每天早晨，FJ 从家中穿过农场走到牛棚。农场由 块农田组成，农田通过 条双向道路连接，每条路有一定长度。FJ 的房子在 号田，牛棚在 号田。没有两块田被多条道路连接，以适当的路径顺序总是能在农场任意一对田间行走。当 FJ 从一块田走到另一块时，总是以总路长最短的道路顺序来走。
FJ 的牛呢，总是不安好心，决定干扰他每天早晨的计划。它们在 条路的某一条上安放一叠稻草堆，使这条路的长度加倍。牛希望选择一条路干扰使得 FJ 从家到牛棚的路长增加最多。它们请你设计并告诉它们最大增量是多少。
第 行：两个整数 。
第 到 行：第 行包含三个整数 ， 和 表示道路 连接的田的编号， 表示路长。
一个整数，表示通过使某条路加倍而得到的最大增量。
5 7 2 1 5 1 3 1 3 2 8 3 5 7 3 4 3 2 4 7 4 5 2
2
【样例说明】
若使 和 之间的道路长加倍，最短路将由 变为 。
【数据规模和约定】
对于 的数据，，。
对于 的数据，，，。
