#9310. 「USACO11DEC」 Roadblock S 普及+/提高

每天早晨，约翰醒来，从他的房子穿过农场走到牛棚。

农场由 块田地组成，这些田地由 条双向道路连接，每条道路都有一定的长度。

约翰的房子位于田地 ，牛棚位于田地 。

没有任何一对田地通过多个冗余道路相连，任何一对田地之间都存在连通路径。

当从一片田地走到另一片田地时，约翰总是会选择一系列具有最小总长度的道路组成的路线。

约翰的奶牛们总是不安好心，企图干扰他早上的例行公事。

它们计划在农场的 条道路中，选择一条在上面铺满干草，使得该道路的长度翻倍。

奶牛们希望借此尽可能的增加约翰从房子到牛棚所需行走的距离。

请你确定奶牛们可以将约翰的行进路线延长多少距离。

第 行包含两个整数 和 。

第 行，第 行描述第 条双向道路，包含三个整数 ，表示田地 与 之间存在一条长度为 的道路。

输出通过使某条道路长度加倍，能使约翰的行进路线延长的最大距离。

样例输入

5 7
2 1 5
1 3 1
3 2 8
3 5 7
3 4 3
2 4 7
4 5 2

样例输出

2

样例解释

初始状态下，最短路线为 ，长度为 。

一种最佳方案是使 的道路长度由 变为 ，则此时，约翰的最短路线变为 ，长度为 。

行进路线延长了 。

,
,
,