题目描述

机器人刚刚探查归来，探险队员们突然发现自己的脚下出现了一朵朵白云，把他们托向 了空中。一阵飘飘然的感觉过后，队员们发现自己被传送到了一座空中花园。

"远道而来的客人，我们是守护 $\red{Nescafe }$之塔的精灵。如果你们想拜访护法和圣主的话， 就要由我们引路。因此，你们是不是该给我们一点礼物呢 $\red{T\_T}$？"

队员们往远处一看，发现花园中有 $\red{N }$个木箱，$\red{M }$条柔软的羊毛小路，每条小路的两个 端点都是木箱，并且通过它需要 $\red{t_i }$的时间。队员们需要往每个木箱中放一份礼物，不过由 于精灵们不想让花园被过多地踩踏，因此运送礼物的任务最多只能由两位探险队员完成。

两位探险队员同时从 $\red{1 }$号木箱出发，可以在任意木箱处结束运送。运送完毕时，每只木 箱应该被两位队员中至少一人访问过。运送任务所用的时间是两人中较慢的那个人结束运送 任务的时间。请问这个时间最快是多少呢？

输入格式

第一行两个正整数 $\red{N}$、$\red{M}$。

接下来 $\red{M }$行每行三个整数 $\red{x_i}$、$\red{y_i}$、$\red{t_i，}$表示 $\red{x_i }$和 $\red{y_i }$之间有一条用时为 $\red{t_i }$的小路，小路 是双向的。

输出格式

输出所需的最短时间。

样例

输入样例

6 6
1 2 10
2 3 10
3 4 5
4 5 10
5 6 20
2 5 10

输出样例

40

提示

对于 $\red{50\%}$的数据，$\red{1<=N<=9}$。

对于 $\red{100\%}$的数据，$\red{1<=N<=18，}$$\red{1<=t_i<=1000，}$$\red{1<=x_i,y_i<=N，}$两个木箱之间最多只有一 条小路，不会有自己到自己的小路，保证所有木箱是连通的。