You're given a weighted undirected graph with N vertices and M edges. Find the length of the shortest path from vertex 1 to vertex N. Input: First line of the input file contains number of test cases T. Then for each of T test cases described in the following way: First line of the test case contains two integer numbers: N and M. Then M lines follow, each containing three numbers Ai, Bi, Ci, describing edge from Ai to Bi with weight Ci. Output: For each testcase output one line with the only number: the length of the shortest path from vertex 1 to vertex N, or 0 if path does not exist. Constrains: 2 <= N <= 100 0 <= M <= N * ( N - 1 ) / 2 1 <= Ai < Bi <= N 1 <= Ci <= 100 Graph doesn't contain loops or multiedges. Sample input: 1 3 3 1 2 10 2 3 10 1 3 19 Sample output: 19