Sum of Path Weights in a Tree

You are given an undirected tree with n nodes. Each edge of the tree is associated with a weight represented as a triple \(e = (e_1, e_2, e_3)\). For the i-th edge, its triple is \( (e_{i,1}, e_{i,2}, e_{i,3}) \).

Define a function \(\operatorname{win}(x,y)\) for two triples \(x=(x_1,x_2,x_3)\) and \(y=(y_1,y_2,y_3)\) as follows:

• If \(x_2 < y_2\) and \(x_3 < y_3\) then \(\operatorname{win}(x,y) = x_1\).
• If \(x_2 > y_2\) and \(x_3 > y_3\) then \(\operatorname{win}(x,y) = y_1\).
• Otherwise, \(\operatorname{win}(x,y)=0\).

It is easy to see that the \(\operatorname{win}\) function is commutative.

For a sequence of triples \(\{a_1, a_2, \ldots, a_k\}\), define its weight as \(\max_{i=1}^{k-1}\operatorname{win}(a_i,a_{i+1})\). In particular, if \(k=1\) then the weight is defined to be 0.

A path in the tree is defined as the sequence of edges along that path. The weight of a path is the weight of the sequence of edge triples (in the order they are traversed).

Your task is to compute the sum of the weights of all undirected paths in the tree.

inputFormat

The first line contains an integer n (1 ≤ n ≤ N), the number of nodes in the tree.

Each of the next n-1 lines contains five integers: u v e₁ e₂ e₃ representing an edge between nodes u and v with weight triple \((e_1, e_2, e_3)\).

It is guaranteed that the given edges form a tree.

outputFormat

Output a single integer, the sum of the weights of all undirected paths in the tree.

sample

1

0