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 <= 102
1 <= X <= N
N-1 <= M <= 105
1 <= u,v <= N
1 <= w <= 109