Formula 1#820
In the tenth state, there are cities (1 \leq n \leq 800), numbered from to , and bidirectional roads (1 \leq m \leq 4000) connecting these cities. The "Ferrari" team has decided to hold a test session in this state. They plan to conduct races (1 \leq k \leq 40) from the first city to the -th city, ensuring that no two races follow the exact same route. If necessary, some races may use the same road several times. A race ends as soon as the driver reaches the -th city (i.e., the -th city cannot be an intermediate point along the route). To conserve fuel, the "Ferrari" leaders require that the total length of all race routes is minimized. Find this minimum total length.
The first line contains the integers , , and . The next lines each contain three integers, describing the roads: the numbers of the two cities connected by the road and its length (an integer from to ).
Output the required minimum total length. It is guaranteed that there is at least one way to hold all the races.
Example 1