1029 - Communication Networks

Time Limit: 1s Memory Limit: 256MB

Submissions: 149 Solved: 3
Description

The network administrator of a company have to analyze the current state of their communication network all over the world. The communication network consists of servers and cable links between these servers, each link has a cost. A k-route is a sequence of k+1 different servers in which two consecutive servers are connected by a cable link. A cycle is a k-route (for any k > 1) such that the beginning and the terminating servers are connected by a cable link. The communication network contains no cycle. The cost of a k-route is the sum of cost of links between two consecutive servers of the k-route. One of the indicators of the analysis is the k-route having minimal cost of the network for a given value of k.


The 2-route having minimal cost of the communication network in Figure below is 6-1-4 with the cost 3.


Given the communication network G and an integral value k, help the network administrator to find the k-route having minimal cost of G.

Input

The input consists of following lines:

Line 1: contains two integer n and k (1≤ n≤ 10000, 1≤ k≤ 2000) in which n is the number of servers of the communication network G (servers are numbered 1,2,...,n) ;
Line 2: contains an integer m (1≤ m≤ 10000) which is the number of cable links between servers of G;
Line i+2: contains three integers u, v, and w: u and v are two end points of the ith link of G (i = 1,...,m), w is the cost of this link.

Output

The output contains the cost of the k-route found.

Sample Input
6 2
5
1 2 4
1 4 1
1 5 3
1 6 2
2 3 1
Sample Output
3
Hint
Source