Remote Training on Programming

В городе есть N  домов. Некоторые из домов соединены двусторонними дорогами. Никакая дорога не соединяет дом сам с собой. От каждого дома можно пройти к любому другому единственным способом. В городе есть  M разносчиков пенсий. Каждый из них проходит от дома а до дома b  и приносит пенсию в размере t в каждый дом на своем пути. В один дом могут прийти несколько разносчиков. Ваша задача для каждого дома определить, пенсия какого размера в итоге будет в него доставлена. Все дома пронумерованы от 1 до N.

 

Формат входного файла

 

В первой строке входного файла содержится одно целое число N (1<=N<=100000) – количество домов в городе. В следующих N-1 строках заданы дороги в виде пары целых чисел a (1<=a<=N) и b (1<=b<=N) – номера домов, соединенных дорогой (a ≠ b).

В следующей строке задано целое число M (0<=M<=100000) – количество разносчиков пенсий. В следующих M строках содержится по 3 целых числа разделенных пробелом: номера домов a(1<=a<=N), b(1<=b<=N) и размер пенсии   t       (-10⁹<=t<=10⁹)

 

Формат выходного файла

 

Выведите N целых чисел по одному в строке – размер пенсии для каждого дома.

 

Пример

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