It's 4 PM on a Wednesday, and Bevo just finished a 2-hour OS lecture. He signed up for the UTPC contest this evening, and needs some caffeine to keep him going. But unlike every other CS student, Bevo doesn't LinkedInMaxx. Bevo doesn't larp. Bevo doesn't network. Bevo doesn't swing by Up and Atom in Welch for matcha or buy an $8 coffee from Lucky Lab. Bevo only drinks black coffee straight from the pot that costs 2 cents to make, like a middle-aged man who has a wife and three kids at home. To do this, he must quickly head back to his apartment so he can depart for the contest on time.
Consider the GDC as location $$$1$$$ and Bevo's apartment as location $$$N$$$. UT campus has $$$N - 2$$$ street corners, numbered $$$2$$$ through $$$N - 1$$$. Each street connects two of these locations (a corner, the GDC, or the apartment) and is accompanied by an estimated time to walk across it. Streets are two-way. Help Bevo rush home in the shortest possible time so he can refuel.
The first line contains two integers $$$N$$$ and $$$S$$$ ($$$2 \le N \le 10^5$$$, $$$1 \le S \le 2 \cdot 10^5$$$) — the number of locations (including the GDC and the apartment) and the number of streets connecting them.
Each of the next $$$S$$$ lines contains three integers $$$a$$$, $$$b$$$, and $$$c$$$ ($$$1 \le a, b \le N$$$, $$$a \ne b$$$, $$$1 \le c \le 10^9$$$) — a street connecting locations $$$a$$$ and $$$b$$$ that takes $$$c$$$ time to walk from $$$a$$$ to $$$b$$$ or vice versa.
It is guaranteed that at least one path exists from the GDC (location $$$1$$$) to Bevo's apartment (location $$$N$$$).
Print a single integer — the shortest possible time for Bevo to get from the GDC to his apartment.
5 61 2 21 3 42 3 12 4 73 5 34 5 1
6
2 11 2 10
10
In the first example, the fastest route is $$$1 \to 2 \to 3 \to 5$$$ with total time $$$2 + 1 + 3 = 6$$$.
