Campus Navigation Optimization

In a campus, there are ( n ) classrooms numbered from ( 1 ) to ( n ) connected by ( n-1 ) corridors, forming a tree. Each corridor ( i ) has a length ( w_i ), and the time to traverse it equals ( w_i ). Two special classrooms, ( s ) (Steve's) and ( t ) (Ada's), are given. In every other classroom, a marker is set on one of its adjacent corridors. When entering a classroom, one follows the marker and moves along that corridor. Note that no markers are placed outside ( s ) and ( t ) (which have no outgoing markers).

The markers must be placed (i.e. selecting one outgoing edge per classroom except ( s ) and ( t )) such that:

1. Each classroom except ( s ) and ( t ) has exactly one outgoing corridor and ( s, t ) have none.
2. For every classroom, following the marked corridors leads eventually to either ( s ) or ( t ).

The time taken for a classroom is the sum of corridor lengths along the unique path (defined by the markers) to ( s ) or ( t ). The goal is to choose the corridors on which markers are placed such that the total travel time from all classrooms is minimized.

It can be shown that the optimal strategy is for each classroom ( v ) (other than ( s ) and ( t )) to pick the edge on the unique shortest path from ( v ) to ( s ) or ( t ) (whichever yields a lesser distance). Hence, the answer is the sum over all classrooms ( v ) of ( \min(\mathit{d}(v, s), \mathit{d}(v, t)) ), where ( \mathit{d}(\cdot,\cdot) ) denotes the distance computed along the unique path in the tree.

inputFormat

The input begins with a line containing three integers ( n ), ( s ), and ( t ) (with ( 2 \le n \le 10^5 ), ( 1 \le s, t \le n ), and ( s \neq t )). Each of the next ( n-1 ) lines contains three integers ( u ), ( v ), and ( w ) (with ( 1 \le w \le 10^9 )), representing a corridor between classrooms ( u ) and ( v ) of length ( w ).

outputFormat

Output a single integer: the minimum total travel time for all classrooms by following the optimal marker placement scheme.

sample

4 1 4
1 2 3
2 3 2
3 4 4

16