E. Сломанное дерево
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано дерево, состоящее из n вершин, пронумерованных числами от 1 до n, где вершина с номером один — корень дерева. У каждого ребра есть собственные вес wi и прочность pi.

Ботаник Иннокентий, единственный член жюри олимпиады по информатике, очень не любит сломанные деревья.

Дерево является сломанным, если существует такое ребро, прочность которого меньше суммы весов рёбер поддерева, в которое оно ведёт.

Разрешается уменьшать вес любого ребра на целую величину, но тогда прочность этого ребра уменьшается на ту же величину. То есть если вес ребра 10, а прочность 12, то при уменьшении веса на 7 его вес станет равным 3, а прочность станет равной 5.

Увеличивать вес ребра нельзя.

Ваша задача: уменьшая веса рёбер заданного дерева, получить дерево, которое не является сломанным, а также все рёбра в нём должны иметь положительный вес, причём суммарный вес всех рёбер должен быть наибольшим.

Очевидно, что прочность рёбер не может быть отрицательной, однако она может равняться нулю, если вес поддерева равен нулю.

Входные данные

В первой строке входных данных содержится целое число n (1 ≤ n ≤ 2·105) — количество вершин в дереве.

В следующих n - 1 строках содержится описание рёбер. Каждая строка содержит четыре целых числа x, y, w, p (1 ≤ x, y ≤ n, 1 ≤ w ≤ 109, 0 ≤ p ≤ 109), где x и y — вершины, которые соединяет ребро (вершина под номером x — предок вершины под номером y), w и p — вес и прочность ребра соответственно. Гарантируется, что рёбра описывают дерево с корнем в вершине 1.

Выходные данные

Если из заданного дерева нельзя получить несломанное, то выведите в единственной строке -1.

Иначе, выходные данные должны содержать n строк:

В первой строке выведите число n — количество вершин в дереве.

В следующих n - 1 строках выведите описание рёбер конечного дерева. Каждая строка должна содержать четыре целых числа x, y, w, p (1 ≤ x, y ≤ n, 1 ≤ w ≤ 109, 0 ≤ p ≤ 109), где x и y — вершины, которые соединяет ребро (вершина под номером x — предок вершины под номером y), w и p — новые вес и прочность ребра соответственно.

Выводите рёбра в том же порядке, в каком они заданы во входных данных, то есть первые два числа каждой строки должны оставаться неизменёнными.

Примеры
Входные данные
3
1 3 5 7
3 2 4 3
Выходные данные
3
1 3 5 7
3 2 4 3
Входные данные
4
1 3 2 3
3 4 5 1
3 2 3 3
Выходные данные
-1
Входные данные
5
1 2 2 4
2 4 1 9
4 5 5 6
4 3 4 8
Выходные данные
5
1 2 2 4
2 4 1 9
4 5 1 2
4 3 2 6
Входные данные
7
1 2 5 2
2 3 4 3
1 4 3 7
4 5 4 1
4 6 3 2
6 7 1 6
Выходные данные
7
1 2 5 2
2 3 2 1
1 4 3 7
4 5 3 0
4 6 3 2
6 7 1 6