Nindra finds themself in a city of ~n~ buildings, with ~m~ connections between them. Nindra is initially at building ~0~, and wants to reach building ~n-1~. However, each of the connections has a weight ~w~, which refers to how tiring it is for them to traverse that edge. Therefore Nindra wants to travel from building ~0~ to building ~n-1~ with the minimum total cost.

Luckily, Nindra has magic powers! They can ignore up to ~k~ of the edge weights through this journey. As Nindra's ninja teacher, help them figure out the minimum cost they can take on this journey.

Input Format

The first line will consist of three integers, ~n~, ~m~ and ~k~. The next ~m~ lines will consist of 3 integers each, ~i~, ~j~ and ~w~, representing there is a connection between buildings i and j of cost w.

Output Format

The output should consist of a single integer, the minimum cost. There will always be a possible route from building ~0~ to ~n-1~.

Sample Input

3 3 1
0 0 100
0 1 3
1 2 5

Sample Output

3

Sample Explanation

The best path for Nindra to take is 0->1->2, which is cost 3+5 = 8. However, Nindra uses their magical powers on the edge of weight 5, resulting in a total cost of 3.

Constraints

~2 \le n \le 1e5~

~1 \le k \le 10~

~n \le m \le 1e5~

~0 \le i,j \le n-1~

~1 \le w \le 1e3~