P15703 [2018 KAIST RUN Spring] Xtreme NP-hard Problem?!

*Caution!* This problem turned out to be NP-hard. But since there was no rules against writing a NP-hard problem, we decided to leave this problem here. There is a bidirectional graph consisting of $n$ vertices and $m$ edges. The vertices and edges are numbered from 1 to $n$ and 1 to $m$ respectively, and the weight of edge $i$ is $w_i$. ($1 \le i \le m$) Given a natural number $k$, find the length of the shortest simple path that starts from vertex 1 and ends at vertex $n$, and consists of $k$ edges. A simple path is a path that does not visit same vertex twice, and length of a path is the sum of weight of edges that consists the path.

In the first line, three space-separated integers $n$, $m$, $k$ are given. In the next $m$ lines, three space-separated integers $x_i$, $y_i$, $w_i$ are given. They denote that edge $i$ is connecting vertex $x_i$ and vertex $y_i$, and has weight $w_i$. No loops or multiple edges are given.

Print the length of the shortest simple path that starts from vertex 1 and ends at vertex $n$, and consists of $k$ edges. If there is no such path, print $-1$.

### Constraints - $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 n$) - $i \ne j \Rightarrow \{x_i, y_i\} \ne \{x_j, y_j\}$ ($1 \le i, j \le n$) - $1 \le w_i \le 10^8$ - $\min(n,m,k)\le 5$