Bessie планирует ежегодный Большой сбор коров со всей страны и хочет самое удобное место.

Каждая живёт в одном из $N$ ($1 \le N \le 100,000$) амбаров с номерами $1..N$, соединённых $N-1$ дорогами так, что все достижимы. Дорога $i$ связывает $A_{i}$ и $B_{i}$ ($1 \le A_i \le N; 1 \le B_i \le N$), длина $L_{i}$ ($1 \le L_{i} \le 1,000$). Любой из $N$ может принять сбор; в амбаре $i$ живут $C_{i}$ ($0 \le C_{i} \le 1,000$) коров.

Максимум удобства — минимум неудобства. Для амбара $X$ это сумма расстояний всех коров до $X$; если от $i$ до $X$ расстояние 20, они проходят $C_{i}*20$. Помогите выбрать лучший.

Пример пяти амбаров с разным числом коров в скобках и разной длиной дорог. В 3 и 4 нет коров.

      1     3     4     5
      @--1--@--3--@--3--@[2]
     [1]    |
            2
            |
            @[1]
            2

Можно любой из пяти; таблица неудобств: B1–B5 — амбары, последний столбец сумма.

Если сбор в амбаре 1, неудобства по амбарам:

• Амбар 1: 0, ехать не нужно!
• Амбар 2: 3, расстояние $2+1=3$, умноженное на 1 корову даёт 3.
• Амбар 3: 0, нет коров!
• Амбар 4: 0, нет коров!
• Амбар 5: 14, расстояние $3+3+1=7$, умноженное на 2 коровы даёт 14.

Итого неудобство 17.

Лучшее значение 15 при сборе в 3, 4 или 5.

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

• Строка 1: целое $N$.
• Строки $2..N+1$: строка $i+1$ содержит целое $C_{i}$.
• Строки $N+2..2N$: строка $i+N+1$ содержит три целых $A_{i}$, $B_{i}$, $L_{i}$.

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

• Строка 1: минимальное неудобство.

Примеры

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

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

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

15

Автор: Jeffrey Wang, из соревнования, 2010