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 di?erent 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 2 is 6-1-4 with the cost 3.

Given the communication network G and an integral value k, help the network administrator to ?nd 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 (8i = 1;....; m), w is the cost of this link.

Output

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

Example

Input

6 2

5

1 2 4

1 4 1

1 5 3

1 6 2

2 3 1

Output

3