Backpack Buddies

The prudent Mr. Day and the adventurous Dr. Knight have decided to be backpack buddies and go trekking in the gorgeous Norwegian mountains. Of course they will use the trails marked by the Norwegian Trekking Association (DNT), like any sane trekkers would. Every such trail starts and ends at a cabin where it is possible to stay overnight.

Mr. Day likes sleeping comfortably, so he immediately suggested that they sleep in a cabin every night.

Dr. Knight disagreed. She argued that they would arrive at their destination much sooner if they walked as far as possible each day, then slept in tents between two cabins when needed. Mr. Day agreed that reaching the destination quickly was desirable, but he was not willing to give up the comfort of a proper bed.

After a fierce argument, they decided to split up and each follow their own strategy. Assuming they walk at the same pace, how many hours will Dr. Knight need to wait at the final destination before Mr. Day shows up?

The first line contains two integers, $n$ ($1 \le n \le 100000$), the number of cabins, and $m$ ($1 \le m \le 100000$), the number of trails. The next $m$ lines each describe a trail. The $i$-th of these lines contains three integers $u_i$, $v_i$, and $d_i$ ($0 \le u_i, v_i < n$, $0 \le d_i \le 12$), meaning there is a trail between cabins $u_i$ and $v_i$ that takes exactly $d_i$ hours to traverse. There can be more than one trail between two cabins, and a trail can lead back to the cabin it started from.

Mr. Day and Dr. Knight start in cabin 0, and their destination is cabin $n-1$. Each day they start walking at 08:00 and walk non-stop for at most 12 hours before settling down for the night.

Output a single integer, the number of hours Dr. Knight needs to wait at the destination before Mr. Day shows up.