K — Hiking

Lea enjoys nature a lot, therefore she often goes hiking at the weekend. Last Sunday, she got up early, drove to the foot of a mountain and reached the top just at the right time for lunch. During her dessert, “Apfelstrudel”, she suddenly remembered: she had a very important appointment this afternoon which she was about to miss. In a big hurry, she looked at the map to figure out the fastest way to her car. To her amazement, there were hundreds of walking tracks which crossed multiple times forming thousands of possible routes down! Lea was helpless. Luckily she had her satellite phone with her and called… you! After giving you the list of all the tracks, she wants to know how far away from her car she currently is. Help her out!

Input Specification

The first line of the input contains an integer t (1 ≤ t ≤ 20). t test cases follow. Two consecutive test cases are separated by a blank line.

Each test case starts with two integers n and m (1 ≤ n ≤ 1000, 1 ≤ m ≤ 50000), where n is the number of intersections, those are numbered from 1 to n, and m is the number of walking trails. Then m lines follow. The ith line contains three integers v_i, w_i, and c_i (1 ≤ v_i, w_i ≤ n, 1 ≤ c_i ≤ 1000). v_i and w_i each denote an intersection of walking trails, c_i is the length of a walking track connecting those intersections. Walking trails are undirected. Lea is currently at intersection 1, her car is at intersection n.

Output Specification

For each test case, output one line containing “Case #i: d” where i is its number, starting at 1, and d is the shortest distance from intersection 1 to intersection n. Each line of the output should end with a line break.