Problem Statement

Graph Paths II 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 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 minimum path length. If there are no such paths, print -1. 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