Meadow Messenger

# Meadow Messenger ## Problem Statement Bessie the cow needs to deliver an urgent message from her meadow to Farmer John's meadow. There are $N$ meadows connected by $M$ undirected paths, each with a travel time. Bessie wants to find the shortest travel time to deliver her message from meadow $1$ to meadow $N$. ## Input Format The first line contains two integers $N$ and $M$, where $N$ is the number of meadows and $M$ is the number of paths. Each of the next $M$ lines contains three integers $u$, $v$, and $w$, meaning there is a path between meadows $u$ and $v$ with travel time $w$. ## Output Format Output the shortest travel time from meadow $1$ to meadow $N$. If it is impossible to reach meadow $N$ from meadow $1$, output $-1$. ## Constraints - $1 \le N \le 10^5$ - $0 \le M \le 10^5$ - $1 \le w \le 10^9$ (all weights are positive) - $1 \le u, v \le N$ ## Sample Input ``` 4 5 1 2 4 1 3 1 3 2 2 2 4 1 3 4 7 ``` ## Sample Output ``` 4 ``` ## Explanation The graph has 4 meadows and 5 paths: - Meadow 1 to 2: travel time 4 - Meadow 1 to 3: travel time 1 - Meadow 3 to 2: travel time 2 - Meadow 2 to 4: travel time 1 - Meadow 3 to 4: travel time 7 The shortest path from meadow 1 to meadow 4 is: 1 → 3 → 2 → 4, with a total travel time of 1 + 2 + 1 = 4.