In question 1 implement Dijkstra’s algorithm instead of a BFS. The edges are denoted by “u v w”, denoting an edge from the vertex u to the vertex v with a weight of w.

The tie breaking condition is that a vertex prefers a smaller parent. The vertices are all unique.

Sample Input

1

7 14

0 5 12

5 0 12

0 1 6

1 0 6

1 2 1

2 1 1

2 5 3

5 2 3

0 3 7

3 0 7

3 4 1

4 3 1

4 5 1

5 4 1

Sample Output

0

6

7

7

8

9

-1