{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cstyle type\u003d\"text/css\"\u003e\r\nh1,h2,h3,h4,h5,h6{margin-bottom:0;}div.textBG p{margin: 0 0 0.0001pt;}\u003c/style\u003e\r\n\u003cp\u003e\r\n\t\u003cspan style\u003d\"float:right\"\u003e\u003ca href\u003d\"http://uva.onlinejudge.org/external/106/10600.pdf\" target\u003d\"_blank\"\u003e\u003cimg alt\u003d\"Download as PDF\" border\u003d\"0\" height\u003d\"26\" src\u003d\"http://uva.onlinejudge.org/components/com_onlinejudge/images/button_pdf.png\" title\u003d\"Download as PDF\" width\u003d\"100\" /\u003e\u003c/a\u003e\u003c/span\u003e\u003c/p\u003e\r\n\u003cdiv style\u003d\"clear:both\"\u003e\r\n\t\u0026nbsp;\u003c/div\u003e\r\n\u003cdiv class\u003d\"Section1\"\u003e\r\n\t\u003cdiv style\u003d\"border:solid windowtext 1.0pt;border-bottom:none;padding:1.0pt 4.0pt 0mm 4.0pt;\r\nbackground:silver\"\u003e\r\n\t\t\u003ch1 style\u003d\"background:silver;border:none;padding:0mm\"\u003e\r\n\t\t\t\u003ca href\u003d\"\" name\u003d\"_Toc61410103\"\u003e\u003cspan lang\u003d\"EN-CA\"\u003eProblem A\u003c/span\u003e\u003c/a\u003e\u003c/h1\u003e\r\n\t\t\u003ch2 style\u003d\"background:silver;border:none;padding:0mm\"\u003e\r\n\t\t\t\u003ca href\u003d\"\" name\u003d\"_Toc61410104\"\u003e\u003cspan style\u003d\"font-variant:normal !important;text-transform:uppercase\"\u003eACM contest and Blackout\u003c/span\u003e\u003c/a\u003e\u003c/h2\u003e\r\n\t\u003c/div\u003e\r\n\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\u0026nbsp;\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\tIn order to prepare the \u0026ldquo;The First National ACM School Contest\u0026rdquo;(in 20??) the major of the city decided to provide all the schools with a reliable source of power. (The major is really afraid of \u003cspan data-scayt_word\u003d\"blackoutsJ\" data-scaytid\u003d\"1\"\u003eblackouts\u003cspan style\u003d\"font-family:Wingdings\"\u003eJ\u003c/span\u003e\u003c/span\u003e). So, in order to do that, power station \u0026ldquo;Future\u0026rdquo; and one school (doesn\u0026rsquo;t matter which one) must be connected; in addition, some schools must be connected as well.\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\u0026nbsp;\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\tYou may assume that a school has a reliable source of power if it\u0026rsquo;s connected directly to \u0026ldquo;Future\u0026rdquo;, or to any other school that has a reliable source of power. You are given the cost of connection between some schools. The major has decided to pick out two the cheapest connection plans \u0026ndash; the cost of the connection is equal to the sum of the connections between the schools. Your task is to help the major \u0026ndash; find the cost of the two cheapest connection plans.\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\u0026nbsp;\u003c/p\u003e\r\n\t\u003ch4\u003e\r\n\t\tInput\u003c/h4\u003e\r\n\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\tThe Input starts with the number of test cases, T (1\u0026lt;\u003dT\u003cfont face\u003d\"Symbol\"\u003e\u0026lt;\u003d\u003c/font\u003e15) on a line. Then T test cases follow. The first line of every test case contains two numbers, which are separated by a space, N (3\u003cfont face\u003d\"Symbol\"\u003e\u0026lt;\u003d\u003c/font\u003eN\u0026lt;\u003d100) the number of schools in the city, and M the number of possible connections among them. Next M lines contain three numbers A\u003csub\u003ei\u003c/sub\u003e, B\u003csub\u003ei\u003c/sub\u003e, \u003cspan data-scayt_word\u003d\"Ci\" data-scaytid\u003d\"18\"\u003eC\u003csub\u003ei\u003c/sub\u003e\u003c/span\u003e , where \u003cspan data-scayt_word\u003d\"Ci\" data-scaytid\u003d\"19\"\u003eC\u003csub\u003ei\u003c/sub\u003e\u003c/span\u003e\u0026nbsp; is the cost of the connection (1\u003cfont face\u003d\"Symbol\"\u003e\u0026lt;\u003d\u003c/font\u003eC\u003csub\u003ei\u003c/sub\u003e\u0026lt;\u003d300) between schools A\u003csub\u003ei\u003c/sub\u003e\u0026nbsp; and B\u003csub\u003ei\u003c/sub\u003e. The schools are numbered with integers in the range 1 to N.\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\u0026nbsp;\u003c/p\u003e\r\n\t\u003ch4\u003e\r\n\t\tOutput\u003c/h4\u003e\r\n\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\tFor every test case print only one line of output. This line should contain two numbers separated by a single space - the cost of two the cheapest connection plans. Let \u003cspan data-scayt_word\u003d\"S1\" data-scaytid\u003d\"21\"\u003eS\u003csub\u003e1\u003c/sub\u003e\u003c/span\u003e be the cheapest cost and \u003cspan data-scayt_word\u003d\"S2\" data-scaytid\u003d\"29\"\u003eS\u003csub\u003e2\u003c/sub\u003e\u003c/span\u003e the next cheapest cost. It\u0026rsquo;s important, that \u003cspan data-scayt_word\u003d\"S1\" data-scaytid\u003d\"26\"\u003eS\u003csub\u003e1\u003c/sub\u003e\u003c/span\u003e\u003d\u003cspan data-scayt_word\u003d\"S2\" data-scaytid\u003d\"30\"\u003eS\u003csub\u003e2\u003c/sub\u003e\u003c/span\u003e if and only if there are two cheapest plans, otherwise S\u003csub\u003e1\u003c/sub\u003e\u003cfont face\u003d\"Symbol\"\u003e\u0026lt;\u003d\u003c/font\u003eS\u003csub\u003e2\u003c/sub\u003e. You can assume that it is always possible to find the costs \u003cspan data-scayt_word\u003d\"S1\" data-scaytid\u003d\"34\"\u003eS\u003csub\u003e1\u003c/sub\u003e\u003c/span\u003e and \u003cspan data-scayt_word\u003d\"S2\" data-scaytid\u003d\"35\"\u003eS\u003csub\u003e2\u003c/sub\u003e\u003c/span\u003e..\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\u0026nbsp;\u003c/p\u003e\r\n\t\u003ctable border\u003d\"1\" cellpadding\u003d\"0\" cellspacing\u003d\"0\" class\u003d\"MsoTableList4\" style\u003d\"border-collapse:collapse;border:none\"\u003e\r\n\t\t\u003ctbody\u003e\r\n\t\t\t\u003ctr\u003e\r\n\t\t\t\t\u003ctd style\u003d\"width:246.35pt;border:solid black 1.5pt;\r\n border-right:none;background:gray;padding:0mm 5.4pt 0mm 5.4pt\" valign\u003d\"top\" width\u003d\"328\"\u003e\r\n\t\t\t\t\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\t\t\t\t\u003cb\u003e\u003cspan style\u003d\"color:white\"\u003eSample Input\u003c/span\u003e\u003c/b\u003e\u003c/p\u003e\r\n\t\t\t\t\u003c/td\u003e\r\n\t\t\t\t\u003ctd style\u003d\"width:246.35pt;border:solid black 1.5pt;\r\n border-left:none;background:gray;padding:0mm 5.4pt 0mm 5.4pt\" valign\u003d\"top\" width\u003d\"328\"\u003e\r\n\t\t\t\t\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\t\t\t\t\u003cb\u003e\u003cspan style\u003d\"color:white\"\u003eSample Output\u003c/span\u003e\u003c/b\u003e\u003c/p\u003e\r\n\t\t\t\t\u003c/td\u003e\r\n\t\t\t\u003c/tr\u003e\r\n\t\t\t\u003ctr\u003e\r\n\t\t\t\t\u003ctd style\u003d\"width:246.35pt;border-top:none;border-left:\r\n solid black 1.5pt;border-bottom:solid black 1.5pt;border-right:none;\r\n padding:0mm 5.4pt 0mm 5.4pt\" valign\u003d\"top\" width\u003d\"328\"\u003e\r\n\t\t\t\t\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\t\t\t\t2\u003c/p\u003e\r\n\t\t\t\t\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\t\t\t\t5 8\u003c/p\u003e\r\n\t\t\t\t\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\t\t\t\t1 3 75\u003c/p\u003e\r\n\t\t\t\t\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\t\t\t\t3 4 51\u003c/p\u003e\r\n\t\t\t\t\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\t\t\t\t2 4 19\u003c/p\u003e\r\n\t\t\t\t\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\t\t\t\t3 2 95\u003c/p\u003e\r\n\t\t\t\t\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\t\t\t\t2 5 42\u003c/p\u003e\r\n\t\t\t\t\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\t\t\t\t5 4 31\u003c/p\u003e\r\n\t\t\t\t\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\t\t\t\t1 2 9\u003c/p\u003e\r\n\t\t\t\t\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\t\t\t\t3 5 66\u003c/p\u003e\r\n\t\t\t\t\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\t\t\t\t9 14\u003c/p\u003e\r\n\t\t\t\t\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\t\t\t\t1 2 4\u003c/p\u003e\r\n\t\t\t\t\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\t\t\t\t1 8 8\u003c/p\u003e\r\n\t\t\t\t\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\t\t\t\t2 8 11\u003c/p\u003e\r\n\t\t\t\t\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\t\t\t\t3 2 8\u003c/p\u003e\r\n\t\t\t\t\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\t\t\t\t8 9 7\u003c/p\u003e\r\n\t\t\t\t\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\t\t\t\t8 7 1\u003c/p\u003e\r\n\t\t\t\t\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\t\t\t\t7 9 6\u003c/p\u003e\r\n\t\t\t\t\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\t\t\t\t9 3 2\u003c/p\u003e\r\n\t\t\t\t\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\t\t\t\t3 4 7\u003c/p\u003e\r\n\t\t\t\t\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\t\t\t\t3 6 4\u003c/p\u003e\r\n\t\t\t\t\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\t\t\t\t7 6 2\u003c/p\u003e\r\n\t\t\t\t\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\t\t\t\t4 6 14\u003c/p\u003e\r\n\t\t\t\t\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\t\t\t\t4 5 9\u003c/p\u003e\r\n\t\t\t\t\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\t\t\t\t5 6 10\u003c/p\u003e\r\n\t\t\t\t\u003c/td\u003e\r\n\t\t\t\t\u003ctd style\u003d\"width:246.35pt;border-top:none;border-left:\r\n none;border-bottom:solid black 1.5pt;border-right:solid black 1.5pt;\r\n padding:0mm 5.4pt 0mm 5.4pt\" valign\u003d\"top\" width\u003d\"328\"\u003e\r\n\t\t\t\t\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\t\t\t\t110 121\u003c/p\u003e\r\n\t\t\t\t\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\t\t\t\t37 37\u003c/p\u003e\r\n\t\t\t\t\u003c/td\u003e\r\n\t\t\t\u003c/tr\u003e\r\n\t\t\u003c/tbody\u003e\r\n\t\u003c/table\u003e\r\n\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\u0026nbsp;\u003c/p\u003e\r\n\t\u003cdiv style\u003d\"border:none;border-top:solid windowtext 1.0pt;padding:1.0pt 0mm 0mm 0mm;\r\nbackground:white\"\u003e\r\n\t\t\u003cp class\u003d\"Credits\"\u003e\r\n\t\t\tProblem source: Ukrainian National Olympiad in Informatics 2001\u003c/p\u003e\r\n\t\t\u003cp class\u003d\"Credits\"\u003e\r\n\t\t\tProblem author: \u003cspan data-scayt_word\u003d\"Shamil\" data-scaytid\u003d\"44\"\u003eShamil\u003c/span\u003e \u003cspan data-scayt_word\u003d\"Yagiyayev\" data-scaytid\u003d\"45\"\u003eYagiyayev\u003c/span\u003e\u003c/p\u003e\r\n\t\t\u003cp class\u003d\"Credits\"\u003e\r\n\t\t\tProblem submitter: \u003cspan data-scayt_word\u003d\"Dmytro\" data-scaytid\u003d\"48\"\u003eDmytro\u003c/span\u003e \u003cspan data-scayt_word\u003d\"Chernysh\" data-scaytid\u003d\"50\"\u003eChernysh\u003c/span\u003e\u003c/p\u003e\r\n\t\t\u003cp class\u003d\"Credits\"\u003e\r\n\t\t\tProblem solution: \u003cspan data-scayt_word\u003d\"Shamil\" data-scaytid\u003d\"46\"\u003eShamil\u003c/span\u003e \u003cspan data-scayt_word\u003d\"Yagiyayev\" data-scaytid\u003d\"47\"\u003eYagiyayev\u003c/span\u003e, \u003cspan data-scayt_word\u003d\"Dmytro\" data-scaytid\u003d\"49\"\u003eDmytro\u003c/span\u003e \u003cspan data-scayt_word\u003d\"Chernysh\" data-scaytid\u003d\"51\"\u003eChernysh\u003c/span\u003e, K M \u003cspan data-scayt_word\u003d\"Hasan\" data-scaytid\u003d\"54\"\u003eHasan\u003c/span\u003e\u003c/p\u003e\r\n\t\u003c/div\u003e\r\n\u003c/div\u003e"}}]}