COURIER  The Courier
Byteland is a scarcely populated country, and residents of different cities seldom communicate with each other. There is no regular postal service and throughout most of the year a oneman courier establishment suffices to transport all freight. However, on Christmas Day there is somewhat more work for the courier than usual, and since he can only transport one parcel at a time on his bicycle, he finds himself riding back and forth among the cities of Byteland.
The courier needs to schedule a route which would allow him to leave his home city, perform the individual orders in arbitrary order (i.e. travel to the city of the sender and transport the parcel to the city of the recipient, carrying no more than one parcel at a time), and finally return home. All roads are bidirectional, but not all cities are connected by roads directly; some pairs of cities may be connected by more than one road. Knowing the lengths of all the roads and the errands to be performed, determine the length of the shortest possible cycling route for the courier.
Input
The input begins with the integer t, the number of test cases. Then t test cases follow.
Each test case begins with a line containing three integers: n m b, denoting the number of cities in Byteland, the number of roads, and the number of the courier's home city, respectively (1<=n<=100,1<=b<=m<=10000). The next m lines contain three integers each, the ith being u_{i} v_{i} d_{i}, which means that cities u_{i} and v_{i} are connected by a road of length d_{i} (1<=u_{i},v_{i}<=100, 1<=d_{i}<= 10000). The following line contains integer z  the number of transport requests the courier has received (1<=z<=5). After that, z lines with the description of the orders follow. Each consists of three integers, the jth being u_{j} v_{j} b_{j}, which signifies that b_{j} parcels should be transported (individually) from city u_{j} to city v_{j}. The sum of all b_{j} does not exceed 12.
Output
For each test case output a line with a single integer  the length of the shortest possible bicycle route for the courier.
Example
Sample input: 1 5 7 2 1 2 7 1 3 5 1 5 2 2 4 10 2 5 1 3 4 3 3 5 4 3 1 4 2 5 3 1 5 1 1 Sample output: 43
hide comments
black_shroud:
20200629 17:44:39
awesome question


sandeepd:
20200117 19:54:40
Lovely problem! 

rks14:
20190912 12:52:49
:) 

nadstratosfer:
20190518 04:54:27
A beautiful and hard problem, needing knowledge of several concepts to solve. 2 years ago I had no idea what a graph was and looking back now after a somewhat effortless AC, it was a long way to get here. A very satisfying journey. 

uf0p2rosir:
20190411 21:08:00
Isn't this problem NPComplete? 

uf0p2rosir:
20190411 19:01:00
and 1<=ui,v<=n instead of <=100 ? 

uf0p2rosir:
20190411 18:59:21
Is that b<=n instead of b<=m ? 

venture_walk:
20171017 17:58:39
How do you solve it with memory as less as 3.1MB ?? 

adelmzian:
20170918 19:40:04
any body can explain to me the test case above ? Last edit: 20170918 19:40:26 

akt_1998:
20170622 12:34:26
FLOYD+DP+BITMASK+4 HOURS ;) 
Added by:  adrian 
Date:  20040728 
Time limit:  7s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS PERL6 VB.NET 
Resource:  based on a problem from the VII Polish Collegiate Team Programming Contest (AMPPZ), 2002 