Problem Background

Xiao C is a winner.

Every Wednesday night, Xiao T eats trotters rice at night, while Xiao C has dinner with a girl in the cafeteria.

Every Friday night, Xiao T starts the Ruins Library, while Xiao C chats with a girl.

Today, Xiao T is sleeping, and Xiao C is playing winning checkers with a girl.

Problem Description

Given a tree with $n$ nodes, each edge has a triplet weight. The triplet $e$ for the $i$-th edge is $(e_{i,1}, e_{i,2}, e_{i,3})$.

Define the function $\operatorname{win}(x,y)$:
- 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$.

Where $x = (x_1, x_2, x_3)$ and $y = (y_1, y_2, y_3)$.

Clearly, the $\operatorname{win}$ function is commutative.

Define the weight of a triplet sequence $\{a_n\}$ as $\max_{i=1}^{n-1} \operatorname{win}(a_i, a_{i+1})$, with the special case that when $n = 1$, the weight is $0$.

Define the weight of a path as the weight of the sequence formed by the weights of all edges traversed in order.

Find the sum of the weights of all undirected paths in the tree.

Input Format

The first line contains a positive integer $n$ ($1 \le n \leq 3 \times 10^5$), representing the number of nodes in the tree.

The next $n-1$ lines each contain four integers $u, v, e_{i,1}, e_{i,2}$, where $e_{i,3} = i$.

It is guaranteed that $\{e_{i,1}\}$ and $\{e_{i,2}\}$ are permutations of $1 \sim n-1$.

Output Format

Output a single integer representing the answer.

Sample Input and Output

Sample Input #1

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

Sample Output #1

9

Sample Input #2

7
1 2 3 4
2 3 6 2
2 4 1 3
2 5 4 6
3 6 2 1
5 7 5 5

Sample Output #2

44

见题面 Input 部分

见题面 Output 部分