Problem Background

zrz has entered a bizarre maze and finds himself lost, wanting to escape. He has painstakingly counted all the paths and is almost fainting from exhaustion, so he calls on you for help.

Problem Description

This is a graph with n nodes and m bidirectional edges, where each edge has a distance of w units. zrz is at position 1, and the exit is at position n. However, due to a bug in zrz's thinking, he does not want to take the shortest path but instead the second shortest path. The second shortest path can share edges with the shortest path and can also repeat through some nodes and edges. Note that if there are multiple paths that are the shortest, none of them can be considered the second shortest path. However, zrz feels uneasy if the next node he enters has fewer than k directly connected places (excluding the start and end points).

Input Format

The first line contains three numbers: n, m, k.

The next m lines each contain three numbers: u, v, w, indicating an edge with weight w from u to v. (u, v <= n, w <= 10000)

Output Format

A single number representing the value of the second shortest path from s to t. If it does not exist, output -1.

Sample Input and Output

Sample Input #1

4 4 1
1 2 100
2 4 200
2 3 250
3 4 100

Sample Output #1

450

Sample Input #2

4 4 3
1 2 100
2 4 200
2 3 250
3 4 100

Sample Output #2

500

Notes

For 50% of the data: n <= 10, m <= 10

For 90% of the data: n <= 1000, m <= 20000

For 100% of the data: n <= 5000, m <= 100000

Additionally, k is relatively small.

In Sample 2, the shortest path is 300 (1-2-4). Since from 2 it is not possible to reach 3 (3 is connected to only 2 nodes), the path can be 1-2-1-2-4, making the second shortest path 500.

见题面 Input 部分

见题面 Output 部分