Safety Path
By Umberto Maia, Centro Universitário do Triângulo 
Brazil
By Umberto Maia, Centro Universitário do Triângulo Brazil
You, a specialized computing Lieutenant, was assigned to help the Colonel Rambo that being Italian, prefers to be called Ramboni. Ramboni is the brave commander of allied troops, who fight to maintain order in the region of Algarias.
To perform the tasks, the troops need to eat well and regularly. For this, every day a truck out of the barracks in the city DETI and travels a few miles through several cities until it reaches the destination, the city DEOT where food is plentiful. However, in recent days, the attacks began to occur to steal loading of the truck.
Given this critical scenario, Colonel Ramboni devised a plan. The truck should go in one path and back using other path entirely different. Being that, the truck can not pass in the same roads/freeway twice. If this is not possible, the truck should be stay on destiny to return just the other day. The indefatigable Colonel Ramboni asked one more thing: we have to be quick because the troops can not stay hungry.
The input contains several test cases. Each test case starts with an integer N (2 ≤ N ≤ 100) indicating the number of cities. DETI is the number one city, and the city N is DEOT. The next line contains an integer M representing the number of roads / freeways. The next M lines describe the M roads / freeway. Each line contains three integers, ie, the two cities connected by a road / freeway and the time required to traverse the distance between them (in minutes). No road / highway will take more than 1000m or less than 1m. Each road / freeway connects two different cities. No two cities will be directly connected for more than a road / highway. The last test case is followed by a line containing the number 0.
For each test case, the output should be a line containing a single integer - the number of minutes that the truck will take to go and back from DETI until DEOT. (Consider negligible the time of the truck stay in DEOT). If there is no solution, write "Pernoite.".
| Sample Input | Sample Output |
|
2 1 1 2 999 3 3 1 3 10 2 1 20 3 2 50 9 12 1 2 10 1 3 10 1 4 10 2 5 10 3 5 10 4 5 10 5 7 10 6 7 10 7 8 10 6 9 10 7 9 10 8 9 10 0 |
Pernoite. 80 Pernoite. |