{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003cp\u003e\r\n\tByteland is a scarcely populated country, and residents of different cities \r\n\tseldom communicate with each other. There is no regular postal service and \r\n\tthroughout most of the year a one-man courier establishment suffices to \r\n\ttransport all freight. However, on Christmas Day there is somewhat more work \r\n\tfor the courier than usual, and since he can only transport one parcel at a \r\n\ttime on his bicycle, he finds himself riding back and forth among the cities of \r\n\tByteland.\r\n\u003c/p\u003e\r\n\u003cp\u003e\r\n\tThe courier needs to schedule a route which would allow him to leave his home \r\n\tcity, perform the individual orders in arbitrary order (i.e. travel to the city \r\n\tof the sender and transport the parcel to the city of the recipient, carrying \r\n\tno more than one parcel at a time), and finally return home. All roads are \r\n\tbi-directional, but not all cities are connected by roads directly; some pairs \r\n\tof cities may be connected by more than one road. Knowing the lengths of all \r\n\tthe roads and the errands to be performed, determine the length of the shortest \r\n\tpossible cycling route for the courier.\r\n\u003c/p\u003e\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003e\r\n\tThe input begins with the integer t, the number of test cases. Then t test \r\n\tcases follow.\r\n\u003c/p\u003e\r\n\u003cp\u003e\r\n\tEach test case begins with a line containing three integers: n m b, denoting \r\n\tthe number of cities in Byteland, the number of roads, and the number of \r\n\tthe courier\u0027s home city, respectively (1 \u0026lt;\u003d b \u0026lt;\u003d n \u0026lt;\u003d 100, 1 \u0026lt;\u003d m \u0026lt;\u003d 10000). The \r\n\tnext m lines contain three integers each, the i-th being u\u003csub\u003ei\u003c/sub\u003e v\u003csub\u003ei\u003c/sub\u003e\r\n\td\u003csub\u003ei\u003c/sub\u003e, which means that cities u\u003csub\u003ei\u003c/sub\u003e and v\u003csub\u003ei\u003c/sub\u003e are \r\n\tconnected by a road of length d\u003csub\u003ei\u003c/sub\u003e (1 \u0026lt;\u003d u\u003csub\u003ei\u003c/sub\u003e, v\u003csub\u003ei\u003c/sub\u003e \u0026lt;\u003d 100, \r\n\t1 \u0026lt;\u003d d\u003csub\u003ei\u003c/sub\u003e \u0026lt;\u003d 10000). The following line contains integer z - the \r\n\tnumber of transport requests the courier has received (1\u0026lt;\u003dz\u0026lt;\u003d5). After that, z \r\n\tlines with the description of the orders follow. Each consists of three \r\n\tintegers, the j-th being u\u003csub\u003ej\u003c/sub\u003e v\u003csub\u003ej\u003c/sub\u003e b\u003csub\u003ej\u003c/sub\u003e, which \r\n\tsignifies that b\u003csub\u003ej\u003c/sub\u003e parcels should be transported (individually) from \r\n\tcity u\u003csub\u003ej\u003c/sub\u003e to city v\u003csub\u003ej\u003c/sub\u003e. The sum of all b\u003csub\u003ej\u003c/sub\u003e does not \r\n\texceed 12.\r\n\u003c/p\u003e\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003e\r\n\tFor each test case output a line with a single integer - the length of the \r\n\tshortest possible bicycle route for the courier.\r\n\u003c/p\u003e\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\u003cdiv\u003e\u003ctable class\u003d\"vjudge_sample\"\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\u003e\r\n1\r\n5 7 2\r\n1 2 7\r\n1 3 5\r\n1 5 2\r\n2 4 10\r\n2 5 1\r\n3 4 3\r\n3 5 4\r\n3\r\n1 4 2\r\n5 3 1\r\n5 1 1\r\n\r\n\u003cb\u003e\u003c/b\u003e\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\r\n43\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/div\u003e\r\n\n\u003c/div\u003e"}}]}