### 问题描述 每天早晨，小齐都会从他的家走过农场到谷仓。农场是由 $N$ 个田地组成（$1 \leq N \leq 100$），通过 $M$ 条双向路径连接在一起（$1 \leq M \leq 10,000$），每条路径都有一个相关联的长度。小齐的家在第 $1$ 个田地，谷仓在第 $N$ 个田地。没有一对田地是通过多余的重复路径相连的，并且可以通过沿着适当的路径行走在农场的任意两个田地之间。当从一个田地到另一个田地旅行时，小齐总是选择一条路径，其路径总长度最小。 小齐的牛们总是调皮捣蛋，决定干扰小齐的早晨例行公事。它们计划在农场上的一条路径上建立一堆干草，使其长度加倍。牛们希望选择一条路径进行封锁，以便最大化小齐从家到谷仓的行进距离。请帮助牛们确定他们可以增加小齐最短路径长度多少。 ### 输入格式 - 第 $1$ 行: 两个由空格分隔的整数 $N$（$1 \leq N \leq 100$） 和 $M$（$1 \leq M \leq 10,000$）。 - 接下来 $M$ 行：第 $j+1$ 行描述第 $j$ 条双向路径，由三个由空格分隔的整数 $A_j$、$B_j$、$L_j$ 描述，其中 $A_j$ 和 $B_j$ 是范围在 $1$ 到 $N$ 之间的索引，表示路径连接的田地，$L_j$ 是路径的长度（范围在 $1$ 到 $1,000,000$ 之间）。 ### 输出格式 - 第 $1$ 行: 可以通过使单条路径的长度加倍，增加小齐最短路径总长度的最大可能值。 ### 样例输入 ``` 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 N \leq 100$，$1 \leq M \leq 10,000$。