当前没有测试数据。

题目描述

应明澈家的电话铃响起了，里面传出了应明澈的老师焦急的声音：“喂，是应明澈的家长吗？你们的孩子又没来上课，不想参加考试了吗？”一听说要考试，应明澈的父母就心急如焚，他们决定在尽量短的时间内找到应明澈。他们告诉应明澈的老师：“根据以往的经验，应明澈现在必然躲在朋友家里偷玩游戏。现在，我们就从家出发去找应明澈，一旦找到，我们立刻给您打电话。”说完砰的一声把电话挂了。

应明澈居住的城市由N个居住点和若干条连接居住点的双向街道组成，经过街道x需花费 (T_x) 分钟。可以保证，任意两个居住点间有且仅有一条通路。应明澈家在点C，两个朋友分别住在点A和点B。应明澈的老师和应明澈的父母都有城市地图，但应明澈的父母知道点A、B、C的具体位置而应明澈的老师不知。

为了尽快找到应明澈，应明澈的父母会遵守以下两条规则：

1. 若A距离C比B距离C近，先去第一个朋友家找，找不到再去第二个朋友家；反之亦然。
2. 总是沿着两点间唯一通路行走。

应明澈老师知道其父母的寻找规则，但不知A、B、C具体位置，需你求出最坏情况下应明澈父母找到他所需的时间。

输入格式

• 第一行：两个整数N和M，分别代表居住点总数和街道总数。
• 接下来M行：每行包含整数 (U_i)、(V_i)、(T_i)，表示街道i连接居住点 (U_i) 和 (V_i)，经过该街道需花费 (T_i) 分钟，且街道信息无重复。

输出格式

输出一个整数T，即最坏情况下应明澈父母找到他所需花费的时间。

输入输出样例

• 输入 #1

4 3
1 2 1
2 3 1
3 4 1

• 输出 #1

4

数据范围

对于100%的数据，(3 \leq N \leq 2 \times 10^5)，(1 \leq U_i, V_i \leq N)，(1 \leq T_i \leq 10^9) 。