Time Limit: 1s
Memory Limit: 256MB
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.
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.
The output contains the cost of the k-route found.
6 2 5 1 2 4 1 4 1 1 5 3 1 6 2 2 3 1
3