War - Escape Part 2

The war is nearing its end, and your army has advanced all the way to city 1, the enemy capital. Just as you are preparing the final attack, you discover that the easy advance was a trap.

You decide to turn the army back and retreat to city N, the border city, to regroup. The enemy knows the local geography well and expects your army to retreat along one of the shortest routes.

Therefore, every road that can appear in at least one shortest route is considered dangerous because the enemy may ambush it. Given the roads between cities, find the shortest travel time from city 1 to city N while avoiding all dangerous roads.

The first line contains the number of cities N (1 <= N <= 1,000) and the number of roads M (0 <= M <= 5,000).

Each of the next M lines contains three integers a, b, and c. This means there is a bidirectional road between city a and city b, and traveling along that road takes c time.

Print the shortest travel time from city 1 to city N after avoiding every road that the enemy may ambush.