每天早晨，农夫从家中穿过农场走到牛棚。 农场由 N 块农田组成，农田通过 M 条双向道路连接，每条路有一定长度。 农夫的房子在 1 号田，牛棚在 N 号田。 没有两块田被多条道路连接，以适当的路径顺序总是能在农场任意一对田间行走。 当农夫从一块田走到另一块时，总是以总路长最短的道路顺序来走。 农夫的牛总是不安好心，决定干扰他每天早晨的计划。 它们在 M 条路的某一条上安放一叠稻草堆，使这条路的长度加倍。 牛希望选择一条路干扰使得农夫从家到牛棚的路长增加最多。 它们请你设计并告诉它们最大增加的路径是多少。
输入格式
第 1 行：两个整数 N, M。(1 <= N <= 100，1 <= M <= 5000) 第 2 到 M+1 行：第 i+1 行包含三个整数 Ai, Bi, Li。(1 <= Ai, Bi <= N，1 <= Li <= 1000000) Ai 和 Bi 表示道路 i 连接的田的编号，Li 表示路长。