Shortest Distance in Road Network

You are given a road network represented as an undirected weighted graph with \( n \) nodes and \( m \) edges. Each node represents a city and each edge represents a bidirectional road connecting two cities with a positive integer length. There may be multiple roads connecting the same two cities. Your task is to compute the shortest distance from city \( 1 \) to city \( n \). If no such path exists, output \( -1 \).

The distance is defined as the sum of the weights along a path, i.e., \( \text{Distance} = \sum_{edge \in path} w \).

inputFormat

The input is read from stdin and has the following format:

• The first line contains two integers \( n \) and \( m \), representing the number of cities and the number of roads respectively.
• Each of the next \( m \) lines contains three integers \( u \), \( v \), and \( w \), representing a bidirectional road between cities \( u \) and \( v \) with length \( w \).

outputFormat

Output a single integer to stdout, which is the shortest distance from city \( 1 \) to city \( n \). If city \( n \) is unreachable from city \( 1 \), output \( -1 \).

5 6
1 2 2
2 3 4
3 5 1
1 4 1
4 5 3
2 5 6

4