Delivery of kefir
During the regular Intergalactic Summer Computer School (ISCS), the organizers encountered a challenge with delivering kefir for the party. The kefir is produced on planet 1, while the students are located on planet n. This distance causes significant delays, leading to the kefir spoiling before it arrives.
Fortunately, the galactic transport system "Berendey-Express" is gradually introducing new kefir pipelines that can transport kefir at twice the speed of the older models. Specifically, kefir takes two years to travel between any two planets using the old pipelines, but only one year with the new ones.
Naturally, it would be a waste not to utilize these advanced technologies. Therefore, the ISCS director has tasked you with writing a program to determine the fastest route from planet 1 to planet n, given the available kefir pipelines (both new and old).
Input
The first line of the input contains two integers n and m (1 ≤ n ≤ 100000, 0 ≤ m ≤ 100000) - representing the number of planets and the number of kefir pipelines, respectively. The following m lines each contain three natural numbers u_i, v_i, and c_i. The numbers u_i and v_i indicate the planet numbers connected by the i-th kefir pipeline, and c_i (c_i=1 or c_i=2) specifies the number of years required to transfer kefir from one planet to another through the i-th pipeline. Planets are numbered starting from one. Kefir can be transmitted through the pipelines in both directions.
Output
The output should be a single number - the number of years required to deliver kefir from planet 1 to planet n. If delivery is impossible, the output should be "-1".