Bessie's Path Farmer John has announced he will present a lecture on Cowmputer Science in exactly K (1 <= K <= 600) minutes. Knowing there are N (1 <= N <= 5,000) farms conveniently numbered from 1..N in his county, FJ decided to present the lecture in farm N. Bessie is at farm 1 and wants to see FJ's lecture. She is so meticulous that she wants her path to take exactly K minutes (so that she will reach FJ's lecture exactly on time). The cows know all about the roads. The farms are connected by M (1 <= M <= 15,000) two-way roads, and between any two different farms with id's F1_i and F2_i, there is at most one road which Bessie might traverse. Each road requires precisely one minute to traverse, and each road i has its own traversal tax (0 <= T_i <= 32,000). Help Bessie find the cheapest path (minimizing the sum of all the taxes; see below) from farm 1 to farm N in exactly K minutes. It is guaranteed that such a path always exists, and that Bessie has enough money to pay the crossing taxes. PROBLEM NAME: bpath.X INPUT FORMAT: * Line 1: Three space-separated integers: N, M, and K * Lines 2..M+1: Line i+1 describes road i with three space-separated integers: F1_i, F2_i, and T_i SAMPLE INPUT: 5 5 3 1 2 2 1 3 1 2 5 2 3 4 2 4 5 3 OUTPUT FORMAT: * Line 1: The minimum tax that Bessie has to pay. SAMPLE OUTPUT: 6 OUTPUT DETAILS: The path 1 -> 3 -> 4 -> 5 takes exactly 3 minutes to cross and its cost is the sum of taxes: 1 + 2 + 3 = 6. There is no other cheaper path.