谨慎的 Day 先生和爱冒险的 Knight 博士决定结伴去挪威的山区徒步旅行。当然，他们会像任何理智的徒步旅行者一样，使用挪威徒步协会（DNT）标记的步道；这些步道都始于并终于某个可以过夜的小木屋。Day 先生喜欢舒适的睡眠，所以他提议他们每天晚上都住在小木屋里。

然而，Knight 博士有不同的看法；她认为如果他们每天尽可能走得远一些，必要时在两个小木屋之间露营，他们就能更快到达目的地。尽管 Day 先生也同意尽快到达目的地是可取的，但他不愿意牺牲舒适的床铺。

经过激烈的争论，Day 先生和 Knight 博士决定分道扬镳，各自采取自己的策略。假设他们两人的步行速度相同，请问当 Day 先生到达最终目的地时，Knight 博士需要等待多久？

照片由 Arild Finne Nybø 拍摄，CC BY-SA 2.0（来自 Flickr）

输入格式

输入的第一行包含两个整数 $n$ ($1 \le n \le 100\,000$)，表示小木屋的数量，以及 $m$ ($1 \le m \le 100\,000$)，表示步道的数量。接下来的 $m$ 行，每行描述一条步道。第 $i$ 行包含三个整数 $u_i, v_i$ 和 $d_i$ ($0 \le u_i, v_i < n, 0 \le d_i \le 12$)，表示在小木屋 $u_i$ 和 $v_i$ 之间有一条步道，走完它需要恰好 $d$ 小时。（两个小木屋之间可能有多条步道，有些步道可能通回出发的小木屋）。

Day 先生和 Knight 博士从 0 号小木屋出发，目的地是 $n-1$ 号小木屋。他们每天早上 08:00 开始步行，每天最多连续步行 12 小时，然后休息过夜。

输出格式

输出一个整数，表示 Knight 博士在目的地需要等待 Day 先生到达的小时数。

样例

输入 1

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

输出 1

4

输入 2

3 2
0 1 2
1 2 12

输出 2

10