Problem Statement

Graph Paths II You are given a directed, weighted graph with n nodes and m edges. Work out the shortest possible length of a path from node 1 to node n that uses exactly k edges. Input Format: The first input line contains three integers n , m , and k : the number of nodes, edges, and the length of the path. 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 Format: Print the shortest such path length, or -1 if no path of exactly k edges exists. Constraints 1 ≤ n ≤ 100 1 ≤ m ≤ n ( n - 1) 1 ≤ k ≤ 10 9 1 ≤ a , b ≤ n 1 ≤ c ≤ 10 9 Examples: Example 1: Input: 5 20 12 5 3 2 2 5 1 1 3 1 4 4 10 3 5 3 3 2 1 5 1 5 1 2 9 5 2 4 1 2 3 2 2 5 2 3 9 1 5 4 5 4 1 5 2 7 4 5 8 3 3 4 4 3 6 3 3 10 2 1 9 Output: 15