Warrior has two important attributes, magic point$($MP$)$ and health point$($HP$).$ These two values

are determined by the warrior at the beginning.

The magic city can be regarded as an undirected simple connected tree $($data structure$)$ with n nodes

and m edges. the warrior will walk in the city, from any starting leaf node to destination t which is

the root node. Every time the warrior passes an edge, the magic point of the warrior will be reduced

by $1.$ At the same time, there is a monster with attack power on each edge, and the warrior will fight

with it$.$ If the magic point of the warrior before passing this edge is k$,$ and the attack power of the

monster on this edge is w$,$ then the battle when passing this edge will consume max$(0,$ w $$ k$)$ healthy

points.

The warrior wants to ensure that his magic point and health point are both zero when reaching node

t at this time. Please find the minimum health point that the warrior needs at any beginning nodes.

For example, let$$s take n $=2,$ m $=1,$ and t $=1,$ there is only one edge $(1,2)$ with a monster whose

attack power is $9.$ The warrior needs at least $8$ healthy points as the warrior will spend $8=$ max$(0,91)$

healthy points to cross this edge.