农场可以描述为N块草地（1≤N≤10,000），方便起见编号为1…N，牛棚位于草地1。草地之间由M条双向的小路连接（N−1≤M≤50,000）。每条小路有其通过时间，从每块草地出发都存在一条由一些小路组成的路径可以到达牛棚。
草地i中有ci头奶牛。当她们听到晚餐铃时，这些奶牛都沿着一条消耗最少时间的路径前往牛棚。如果有多条路径并列消耗时间最少，奶牛们会选择其中“字典序”最小的路径（也就是说，她们通过在两条路径第一次出现分支的位置优先选择经过编号较小的草地的方式来打破并列关系，所以经过草地7、3、6、1的路径会优先于经过7、5、1的路径，如果它们所消耗的时间相同）。
Farmer John担心牛棚距离某些草地太远。他计算了每头奶牛路上的时间，将所有奶牛消耗的时间相加，称这个和为总移动时间。他想要通过额外添加一条从牛棚（草地1）连接到某块他选择的其他草地的、通过时间为T（1≤T≤10,000）的“近道”来尽可能地减少总移动时间。当一头奶牛在她平时前往牛棚的路上偶然看见这条近道时，如果这条近道能够使她更快地到达牛棚，她就会走这条路。否则，一头奶牛会仍然沿着原来的路径行走，即使使用这条近道可能会减少她的移动时间。
请帮助Farmer John求出通过添加一条近道能够达到的总移动时间减少量的最大值。
5 6 2 1 2 3 4 5 1 2 5 1 3 3 2 4 3 3 4 5 4 5 2 3 5 7
40
The farm is described by a set of N fields (1≤N≤10,000), conveniently numbered 1…N, with the barn residing in field 1. The fields are connected by a set of M bidirectional trails (N−1≤M≤50,000). Each trail has a travel time associated with it, and there is a path from every field to the barn using some set of trails.
Field i contains ci cows. Upon hearing the dinner bell, these cows all walk to the barn along a route that takes the minimum amount of time. If there are several routes tied for the minimum time, the cows take whichever of these is "lexicographically" smallest (i.e., they break ties between two routes by favoring the one using the lower-indexed field at the first place where the routes differ, so for example a path that visits fields 7, 3, 6, 1 would be preferable to one that visits 7, 5, 1, assuming both had the same travel time).
Farmer John is worried about the barn being far away from some fields. He adds up the travel time experienced by each cow, summed over all the cows, calling this number the total travel time. He would like to reduce this number as much as possible by adding one extra "shortcut" trail which has a travel time of T (1≤T≤10,000), from the barn (field 1) to some other field of his choosing. If a cow stumbles upon the shortcut trail while traveling along her usual path to the barn, she will take it if it gets her to the barn faster. Otherwise, a cow will follow her usual route, even if it might have been possible to use the shortcut to improve her travel time.
Please help Farmer John determine the greatest possible amount of decrease in total travel time he can achieve by adding his shortcut trail.
5 6 2 1 2 3 4 5 1 2 5 1 3 3 2 4 3 3 4 5 4 5 2 3 5 7
40
5 6 2
1 2 3 4 5
1 2 5
1 3 3
2 4 3
3 4 5
4 5 2
3 5 740