{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv\u003e\u003cp\u003eFarmer John wants to set up a telephone line at his farm. Unfortunately, the phone company is uncooperative, so he needs to pay for some of the cables required to connect his farm to the phone system.\u003c/p\u003e\u003cp\u003eThere are \u003ci\u003eN\u003c/i\u003e (1 ≤ \u003ci\u003eN\u003c/i\u003e ≤ 1,000) forlorn telephone poles conveniently numbered 1..\u003ci\u003eN\u003c/i\u003e that are scattered around Farmer John\u0027s property; no cables connect any them. A total of \u003ci\u003eP\u003c/i\u003e (1 ≤ \u003ci\u003eP\u003c/i\u003e ≤ 10,000) pairs of poles can be connected by a cable; the rest are too far apart.\u003c/p\u003e\u003cp\u003eThe \u003ci\u003ei\u003c/i\u003e-th cable can connect the two distinct poles \u003ci\u003eA\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e and \u003ci\u003eB\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e, with length \u003ci\u003eL\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e (1 ≤ \u003ci\u003eL\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e ≤ 1,000,000) units if used. The input data set never names any {\u003ci\u003eA\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e, \u003ci\u003eB\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e} pair more than once. Pole 1 is already connected to the phone system, and pole\u003ci\u003e N\u003c/i\u003e is at the farm. Poles 1 and \u003ci\u003eN \u003c/i\u003eneed to be connected by a path of cables; the rest of the poles might be used or might not be used.\u003c/p\u003e\u003cp\u003eAs it turns out, the phone company is willing to provide Farmer John with \u003ci\u003eK\u003c/i\u003e (0 ≤ \u003ci\u003eK\u003c/i\u003e \u0026lt; \u003ci\u003eN\u003c/i\u003e) lengths of cable for free. Beyond that he will have to pay a price equal to the length of the longest remaining cable he requires (each pair of poles is connected with a separate cable), or 0 if he does not need any additional cables.\u003c/p\u003e\u003cp\u003eDetermine the minimum amount that Farmer John must pay.\u003c/p\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e* Line 1: Three space-separated integers: \u003ci\u003eN\u003c/i\u003e, \u003ci\u003eP\u003c/i\u003e, and \u003ci\u003eK\u003c/i\u003e\u003cbr\u003e* Lines 2..\u003ci\u003eP\u003c/i\u003e+1: Line \u003ci\u003ei\u003c/i\u003e+1 contains the three space-separated integers: \u003ci\u003eA\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e, \u003ci\u003eB\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e, and \u003ci\u003eL\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e \u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e* Line 1: A single integer, the minimum amount Farmer John can pay. If it is impossible to connect the farm to the phone company, print -1.\u003c/p\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 7 1\r\n1 2 5\r\n3 1 4\r\n2 4 8\r\n3 2 3\r\n5 2 9\r\n3 4 7\r\n4 5 6\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}