### 问题描述 农夫小齐每天早晨都要从他的家走到牛棚。农场中有 $N$ 片田地 $(1 \leq N \leq 250)$，由 $M$ 条双向路径 $(1 \leq M \leq 25,000)$ 连接，每条路径都有一个关联的长度。小齐的家在第 $1$ 片田地，牛棚在第 $N$ 片田地。农场内没有重复的冗余路径，并且可以通过沿着适当路径行走在任意两片田地之间移动。当从一片田地到另一片田地旅行时，小齐总是选择一条路径，该路径的总长度最小。 农夫小齐的奶牛们总是调皮捣蛋，决定干扰他的早晨活动。它们计划在农场的 $M$ 条路径中的一条上堆放一堆干草，使得这条路径的长度加倍。奶牛们希望选择一条路径来阻塞，以便最大化小齐从家到牛棚的距离。请帮助奶牛们确定它们可以通过将一条路径的长度加倍来增加小齐最短路径的长度。 ### 输入格式 第 $1$ 行：两个以空格分隔的整数 $N$ 和 $M$。 第 $2$ 行至第$M+1$行：第 $j+1$ 行描述第 $j$ 条双向路径，其中有三个以空格分隔的整数：$A_j$、$B_j$ 和 $L_j$，表示路径连接的田地索引（在 $1$ 到 $N$ 范围内），以及路径的长度（在 $1$ 到 $1,000,000$ 范围内）。 ### 输出格式 通过将单个路径的长度加倍，小齐最短路径的总长度最大可能增加的值。 ### 样例输入 ``` 5 7 2 1 5 1 3 1 3 2 8 3 5 7 3 4 3 2 4 7 4 5 2 ``` ### 样例输出 ``` 2 ``` ### 评测数据规模 $1 \leq L_j \leq 1,000,000$，$1 \leq N \leq 250$，$1 \leq M \leq 25,000$。