Задача Гонец

Описание

В некотором государстве есть N городов, пронумерованных от 1 до N. Город под номером 1 – столица государства. Дороги соединены двунаправленными N-1 дорогами. Расстояние между городами измеряются в километрах. Граф дорог представляет собой дерево. Если один из городов атакуют враги, то гонец должен передать сообщение в столицу. Гонец характеризуется временем подготовки сообщения и скоростью движения (количество минут для прохождения одного километра).

Сообщение из атакуемого города в столицу должен дойти за минимальное время. В начале гонец атакующего города берет сообщение и выходит в путь. В каждом из посещенных им городов у него есть выбор: двигаться дальше в следующий город или передать сообщение гонцу этого города. Новый гонщик двигается по такому же алгоритму.

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

Формат входных данных

Во входном файла сначала записано число N – количество городов в стране. Далее следуют N-1 строк с числами u, v, d, разделенными одним пробелом, характеризующие дороги. d – длина дороги в километрах, соединяющий города u и v. Далее следуют N – 1 пара чисел Si, Vi описывающие гонцов (i+1)-го города. Si – количество минут для подготовки сообщения, Vi – количество минут, для прохождения одного километра. В столице гонца нету.
3<=N<=100 000
0<= Si<=10 ⁹
0<= Vi<=10 ⁹
Длина каждой дороги не превышает 10 000.

Формат выходных данных

Выведите в выходной файл N-1 чисел – минимальное время в минутах, за которое сообщение можно передать из (i+1)-го города .