Xtreme NP-hard Problem?!

주의! 이 문제는 NP-hard로 밝혀졌습니다. 하지만 NP-hard 문제를 출제하면 안 된다는 규정이 없었기 때문에 그냥 두기로 했습니다.

정점 $n$개와 간선 $m$개로 이루어진 양방향 그래프가 있다. 정점에는 1번부터 $n$번까지, 간선에는 1번부터 $m$번까지 번호가 붙어 있고, $i$번 간선의 가중치는 $w_i$이다.

자연수 $k$가 주어질 때, 1번 정점에서 출발해 $n$번 정점에서 끝나면서 간선을 정확히 $k$개 사용하는 단순 경로 중 가장 짧은 것의 길이를 구하여라.

단순 경로는 같은 정점을 두 번 지나지 않는 경로이고, 경로의 길이는 그 경로를 이루는 간선의 가중치 합이다.

첫째 줄에 세 정수 $n$, $m$, $k$가 공백으로 구분되어 주어진다.

다음 $m$개 줄 중 $i$번째 줄에는 세 정수 $x_i$, $y_i$, $w_i$가 공백으로 구분되어 주어진다. $i$번 간선이 $x_i$번 정점과 $y_i$번 정점을 잇는 가중치 $w_i$의 간선이라는 뜻이다.

루프와 다중 간선은 주어지지 않는다.

1번 정점에서 출발해 $n$번 정점에서 끝나면서 간선을 정확히 $k$개 사용하는 가장 짧은 단순 경로의 길이를 출력한다. 그러한 경로가 없으면 -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$