Minimum Cost Path :
Difficulty Level : Hard
Submissions : 1978
Asked In :
Marks :50
: 18 | : 0
Given a weighted directed graph with n nodes and m edges, find the minimum cost of a path from node 0 to node n-1 that contains at most k edges. if no such path exist print -1.
cost of a particular path between two nodes is defined as the maximum weight of any edge that exists in the path.
Input
First line contains three integers n, m and k (number of nodes , number of edges, maximum number of edges allowed in path).
In next m lines each line represents an edge as u, v and w ( an edge between u and v with w weight).
Output
print a single digit answer denoting the minimum cost of path with at most k edges.
Examples
Input
4 5 2 0 1 5 1 3 6 0 2 6 2 3 5 2 2 5
Output
6
Input
5 5 2 0 1 5 1 2 6 2 4 6 0 3 5 3 4 5
Output
5
