CF758E.Broken Tree

You are given a tree that has n vertices, which are numbered from 1 to n, where the vertex number one is the root. Each edge has weight w__i and strength p__i.

Botanist Innokentiy, who is the only member of the jury of the Olympiad in Informatics, doesn't like broken trees.

The tree is broken if there is such an edge the strength of which is less than the sum of weight of subtree's edges to which it leads.

It is allowed to reduce weight of any edge by arbitrary integer value, but then the strength of its edge is reduced by the same value. It means if the weight of the edge is 10, and the strength is 12, then by the reducing the weight by 7 its weight will equal 3, and the strength will equal 5.

It is not allowed to increase the weight of the edge.

Your task is to get the tree, which is not broken, by reducing the weight of edges of the given tree, and also all edged should have the positive weight, moreover, the total weight of all edges should be as large as possible.

It is obvious that the strength of edges can not be negative, however it can equal zero if the weight of the subtree equals zero.

给你一棵包含 $n$ 个顶点的树，顶点编号为 $1$ 到 $n$，其中顶点 $1$ 为根节点。每条边具有权重 $w_i$ 和强度 $p_i$。

信息学奥林匹克竞赛唯一评委——植物学家因诺肯季（Innokentiy）不喜欢“破损”的树。

当存在某条边，其强度小于该边所指向子树中所有边的权重之和时，这棵树即被视为“破损”。

允许将任意边的权重减少任意整数值；但此时该边的强度也必须同步减少相同数值。例如：若某条边的权重为 $10$、强度为 $12$，将其权重减少 $7$ 后，其权重变为 $3$，强度变为 $5$。

不允许增加任何边的权重。

你的任务是通过对给定树的若干边进行权重缩减操作，使得最终得到一棵非破损的树；此外，所有边的权重必须为正数，且所有边的总权重应尽可能大。

显然，边的强度不能为负数；但若某子树中所有边的权重之和为零，则对应边的强度可为零。

The first line contains the integer n (1 ≤ n ≤ 2·105) — the number of vertices in the tree. The next n - 1 lines contains the description of edges. Each line contains four integers x, y, w, p (1 ≤ x, y ≤ n, 1 ≤ w ≤ 109, 0 ≤ p ≤ 109), where x and y — vertices which connect the edge (the vertex number x is the parent of the vertex number y), w and p are the weight and the strength of the edge, accordingly. It is guaranteed that the edges describe the tree with the root in the vertex 1.

第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$）——树中顶点的数量。接下来的 $n-1$ 行描述了树的边。每行包含四个整数 $x$、$y$、$w$、$p$（$1 \leq x, y \leq n$，$1 \leq w \leq 10^9$，$0 \leq p \leq 10^9$），其中 $x$ 和 $y$ 是该边所连接的两个顶点（顶点 $x$ 是顶点 $y$ 的父节点），$w$ 和 $p$ 分别是该边的权重和强度。保证这些边构成一棵以顶点 $1$ 为根的树。

If it is impossible to get unbroken tree from the given tree, print -1 in the only line.

Otherwise, the output data should contain n lines:

In the first line print the number n — the number of vertices on the tree.

In the next n - 1 lines print the description of edges of the resulting tree. Each line should contain four integers x, y, w, p (1 ≤ x, y ≤ n, 1 ≤ w ≤ 109, 0 ≤ p ≤ 109), where x and y — vertices, which the edge connects (the vertex number x is the parent of the vertex number y), w and p are the new weight and the strength of the edge, accordingly.

Print edges in the same order as they are given in input data: the first two integers of each line should not be changed.

如果无法从给定的树中得到一棵“无断裂”的树，则在唯一一行中输出 -1。

否则，输出应包含 n 行：

第一行输出整数 n —— 树中顶点的数量。

接下来的 n - 1 行输出所得树的边的描述。每行应包含四个整数 x、y、w、p（其中 $1 ≤ x, y ≤ n$，$1 ≤ w ≤ 10^9$，$0 ≤ p ≤ 10^9$），其中 x 和 y 是该边所连接的两个顶点（顶点编号 x 是顶点编号 y 的父节点），w 和 p 分别为该边的新权重和新强度。

边的输出顺序应与输入数据中的顺序一致：每行的前两个整数不得更改。