Xtreme NP-hard Problem?!

Careful! This problem turned out to be NP-hard. No rule forbade setting an NP-hard problem, so it was left as it is.

You are given an undirected graph with $n$ vertices and $m$ edges. The vertices are numbered 1 to $n$, the edges are numbered 1 to $m$, and edge $i$ has weight $w_i$.

Given a natural number $k$, find the length of the shortest simple path that starts at vertex 1, ends at vertex $n$, and uses exactly $k$ edges.

A simple path is a path that never visits the same vertex twice, and the length of a path is the sum of the weights of the edges on it.

The first line contains three integers $n$, $m$, $k$ separated by spaces.

The $i$-th of the next $m$ lines contains three integers $x_i$, $y_i$, $w_i$ separated by spaces. This means edge $i$ joins vertex $x_i$ and vertex $y_i$ and has weight $w_i$.

The graph contains no loops and no multiple edges.

Print the length of the shortest simple path that starts at vertex 1, ends at vertex $n$, and uses exactly $k$ edges. If no such path exists, print -1.

• $2 \le n < 10^6$
• $1 \le m, k < 10^6$
• $1 \le x_i, y_i \le n$
• $x_i \ne y_i$ $(1 \le i \le m)$
• $i \ne j \Rightarrow \{x_i, y_i\} \ne \{x_j, y_j\}$ $(1 \le i, j \le m)$
• $1 \le w_i \le 10^8$