410222: GYM103985 H Соляной рудник

H. Соляной рудникограничение по времени на тест2 секундыограничение по памяти на тест512 мегабайтвводстандартный вводвыводстандартный вывод

Влад приехал на экскурсию на соляной рудник, состоящий из n соляных пещер. Как Влад узнал от экскурсовода, эти пещеры соединены n - 1 туннелями, пронумерованными от 1 до n - 1. Кроме того, известно, что можно дойти от любой пещеры до любой другой пещеры, используя только данные туннели. Изучив карту рудника, Влад оценил для каждого туннеля его красоту. Для того, чтобы насладиться красотой природных объектов, необходимо смотреть на них с нужного ракурса. Поэтому красота туннеля зависит от того, в какую сторону идти по нему.

Для каждого туннеля i, соединяющего пещеры с номерами u_i и v_i, Влад определил два числа p_i и q_i — красоту туннеля, если пройти его от u_i до v_i и красоту туннеля, если пройти его от v_i до u_i соответственно. Красоты задаются целыми числами и могут быть отрицательными в случае, если соответствующий туннель показался Владу некрасивым.

Сейчас Влад находится в пещере с номером 1 и хочет дойти до пещеры с номером n, максимизировав сумму красот туннелей, которые он посмотрит за время своего путешествия. Однако Влад всё же боится заблудиться, поэтому вдоль каждого туннеля он хочет пройти не более, чем один раз в каждую сторону. Помогите Владу определить наиболее красивый маршрут.

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

В первой строке задано целое число n (1 ≤ n ≤ 100 000) — количество пещер в руднике.

В следующих n - 1 строках задано описание туннелей. Каждое описание состоит из четвёрки чисел u_i, v_i, p_i, q_i (1 ≤ u_i, v_i ≤ n, u_i ≠ v_i,  - 10⁴ ≤ p_i, q_i ≤ 10⁴) — номеров пещер, которые соединяет i-й туннель и значений его красоты при движении от u_i к v_i и при движении от v_i к u_i соответственно.

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

Выведите одно целое число — максимально возможную красоту маршрута от пещеры с номером 1 до пещеры с номером n.

ПримерыВходные данные

3
1 2 5 2
2 3 1 3

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

6

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

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

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

3

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

4
1 4 1 1
2 3 -10 2
4 2 7 -6

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

2

Примечание

В первом тестовом примере Владу выгодно пойти из пещеры 1 в пещеру 2, а затем — из пещеры 2 в пещеру 3. В таком случае суммарная красота маршрута составит 5 + 1 = 6.

Во втором тестовом примере Владу выгодно пройти из пещеры 1 в пещеру 4, затем вернуться в пещеру 1, а затем дойти до пещеры 5 через пещеру 2. Суммарная красота в таком случае равна 2 + ( - 1) + 1 + 1 = 3.

В третьем тестовом примере Владу выгодно дойти из пещеры 1 в пещеру 4, затем из пещеры 4 в пещеру 2 и вернуться в пещеру 4. Красота в таком случае равна 1 + 7 + ( - 6) = 2.