Xtreme NP-hard Problem?!

Time limit5sMemory limit1024 MB

Summary

Find the minimum-weight simple path from vertex 1 to vertex n that uses exactly k edges, or report -1; with n, m, k up to 10^6 this is explicitly NP-hard.

Level: Hard9 of 10
Topics: Graph, Shortest path, Dynamic programming, Brute force
Solved: No attempts yet

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.

Input

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.

Output

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.

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 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$

Examples3

Example 1

Input

Expected output

Example 2
Input
```
2 1 1
1 2 7
```
Expected output
```
7
```
Example 3
Input
```
4 4 2
1 2 5
2 3 5
3 4 5
4 1 5
```
Expected output
```
-1
```