Problem D

Rough Roads

Input: standard input

Output: standard output

Time Limit: 18 seconds

Memory Limit: 32 MB

 

After he bought the tri-cycle last year, Shaon went to visit his grandfather's house in a remote part of Bangladesh. He wanted to ride the cycle in quiet, rush-free rural roads. But when he reached the gate of the village of his grandfather, his found his plan useless. The roads are too rough to ride the cycle comfortably. If he rides the cycle from one junction to another, his toe would become too tired to push the paddles in the next part of his journey. He just has to carry the cycle on his back to reach next junction. After that, he will be able to ride the bike again. This would go on until he reaches his grandfather's house. But he doesn't want to knock his grandfather's door with a cycle on his back. So he must travel the last road riding the cycle. He also decided to start his journey by carrying the cycle on his back, not by riding it.

 

Can you find out the shortest way to reach his grandfather's house?

The Input

Input consists of several datasets and is terminated by end of file. The first line of each test case contains two integers: n (the number of junctions, 1 < n < 501) and r (the number of bi-directional roads connecting these junctions). The junctions are numbered with 0, 1, ..., n-1. The gate of the village and the grandfather's house is situated at junctions 0 and n-1 respectively. Each of the next r lines (one for each road) contains three non-negative integers: two junction-numbers that the corresponding road connects and the length of the road in kilometers. A road always connects two different junctions. Length of a road is not more than 20km and not less than 1km.

 

The Output

For each dataset, print the set number (1, 2,...) in a line followed by the length of the shortest path. However, if it is not possible to reach there in the specified way, print a '?'.

Sample Input

3 3

0 1 10

0 2 10

1 2 10

4 4

0 1 10

0 2 10

1 2 10

2 3 10

Sample Input

Set #1

20

Set #2

20


Mustaq Ahmed