Farmer John's Minimal Treats

Farmer John must deliver a package to Farmer Dan by traversing a network of barns connected with bidirectional cow paths. Each path has a given number of cows, and John must feed one treat to each cow he meets. He wants to minimize the total number of treats used. Formally, if his path consists of edges with cow counts (c_i), then the total treats is given by:

[ \text{Treats} = \sum_{i \in \text{path}} c_i ]

Find the minimal number of treats required to travel from barn 1 to barn N.

The map is described by \(N\) barns and \(M\) bi-directional cow paths. Multiple paths may connect the same pair of barns.

inputFormat

The first line contains two integers (N) and (M) where (1 \leq N \leq 50000) and (1 \leq M \leq 50000). Each of the following (M) lines contains three integers (A_i), (B_i), and (c_i) (with (0 \leq c_i \leq 1000)), indicating a bidirectional cow path between barns (A_i) and (B_i) with (c_i) cows.

outputFormat

Output a single integer representing the minimum number of treats that Farmer John needs to bring.

sample

6 8
1 2 1
1 4 4
2 3 6
2 4 0
3 4 4
4 5 3
3 6 2
5 6 1

5