Formula 1
In the thirtieth state, there are n cities (1 ≤ n ≤ 800), numbered from 1 to n, and m bidirectional roads (1 ≤ m ≤ 4000) connecting these cities. The "Ferrari" team has decided to hold a test session in this state. They plan to conduct k races (1 ≤ k ≤ 40) from the first city to the n-th city, ensuring that no two races follow the exact same route. Additionally, races are permitted to use the same road multiple times if necessary. A race concludes once the driver reaches the n-th city, meaning the n-th city cannot be used as an intermediate stop along the route. To conserve fuel, the "Ferrari" team aims to minimize the total length of all race routes combined. Your task is to determine this minimum total length.
Input
The first line contains three integers: k, n, and m. The next m lines each contain three integers, representing the roads: the two cities connected by the road and the road's length (an integer from 1 to 9500).
Output
Output the minimum total length required for all the races. It is guaranteed that there is at least one valid way to conduct all the races.