Points:
1700 (p)
Time limit:
1.0s
Memory limit:
512M
Input:
stdin
Output:
stdout
Consider a directed weighted graph having \(n\) nodes and \(m\) edges. Your task is to calculate the minimum path length from node \(1\) to node \(n\) with exactly \(k\) edges.
Input
- The first input line contains three integers \(n, m\) and \(k\): the number of nodes and edges, and the length of the path. The nodes are numbered \(1,2,\dots,n\).
Then, there are m lines describing the edges. Each line contains three integers \(a, b\) and \(c\): there is an edge from node \(a\) to node \(b\) with weight \(c\).
Output
- Print the minimum path length. If there are no such paths, print −1.
Constraints
- \(1\leq n\leq 100\)
- \(1\leq m\leq n(n−1)\)
- \(1\leq k\leq 10^9\)
- \(1\leq a,b\leq n\)
- \(1\leq c\leq 10^9\)
Example
Sample input
3 4 8
1 2 5
2 3 4
3 1 1
3 2 2
Sample output
27
Comments