The Pokémon Mewtwo was created in a lab from the DNA of Mew. However, it was angry that it is merely a clone and displeased with the concept of being nothing more than a mere lab experiment. Hence, Mewtwo gathered an army of clones to take over the PokéWorld in an epic battle.
PokéTrainer Little Joseph knows he must try to do his best to delay the clones reaching the
frontlines so that Ash, Misty and Brock can be more prepared for the PokéWar. Looking at his Electrode, he knows that the Electrode can self-destruct and destroy one edge in the path of the enemy.
The frontline is marked as node N and where the clone army is now is marked as node 1.
Mewtwo is very smart and can lead his clone army by taking the shortest path possible.
Your task as a PokéProgrammer is to find the best place to put the Electrode, such that the Enemy's fastest possible route after the bombing slowed down as much as possible.
Input
The first line of input contains the 2 integers N and E.
The next E lines of input each contain 3 integers, A, B, W. This means that there is a road between
nodes A and B which takes W time to travel.
For each test case, 0 < W ≤ 1,000 and 0 < N ≤ 500.
Output
Print out the time it will take for the Enemy to move supplies from the base to the frontlines, after the optimal bombing. Print -1 if after you place the bomb there is no route from the base to the frontlines.
Sample Input 1
4 4
1 2 5
2 4 5
1 3 1
3 4 1
Sample Output 1
10