Chintu is a member of the Lolympics committee and is assigned the task of dropping the players from the one stadium to another. There are total N stadiums in Byteland. There is at least one path between any two stadiums. Each stadium has a Dominos outlet near it. Chintu loves pizza and will not drive the bus until and unless he gets one when he's hungry. A trip from one stadium to another can be completed by buying atmost X pizzas for Chintu. He eats pizza at the beginning of each trip which is also counted as one of the X pizzas. Calculate the total minimum distance that Chintu can cover after eating a single pizza i.e. the distance after which Chintu gets hungry and throws tantrums.

Chintu can buy at most one pizza from one stadium.

Input:
The first line consists of N, X and M denoting the number of stadiums, maximum number of times Chintu can buy pizzas and the number of paths between the stadiums.
The next M lines consists of u,v and w denoting that there is a path from stadium u to stadium v of length w.

Output:
A single integer which is the desired distance.

Constraints:
1 <= N <= 10²
1 <= X <= N
N-1 <= M <= 10⁵
1 <= u,v <= N
1 <= w <= 10⁹