{"raw_statement":[{"iden":"statement","content":"给定一颗树，树中每个结点有一个邮递员，每个邮递员要沿着唯一的路径走向 capital（$1$ 号结点），每到一个城市他可以有两种选择：\n\n1. 继续走到下个城市；\n2. 让这个城市的邮递员替他出发。\n\n每个邮递员出发需要一个准备时间 $W_i$，他们的速度是 $V_i$，表示走一公里需要多少分钟。现在要你求出每个城市的邮递员到 capital 的最少时间（不一定是他自己到 capital，可以是别人帮他）？"},{"iden":"input","content":"第一行一个正整数 $N$；\n\n接下来 $N-1$ 行，每行三个正整数 $A,B,C$，表示结点 $A$ 和 $B$ 之间有一条长度为 $C$ 的边；\n\n再接下来 $N-1$ 行，每行 $2$ 个整数 $W_i,V_i$。"},{"iden":"output","content":"输出每个城市的邮递员到 capital 的最少时间。"},{"iden":"note","content":"对于 $20\\%$ 的数据，$N\\leq 2500$；\n\n对于 $50\\%$ 的数据，树是一条链；\n\n对于所有数据，$3\\leq N\\leq 10^5$，$0\\leq W_i,V_i\\leq 10^9$，每条边长度不超过 $10^4$。"}],"translated_statement":null,"sample_group":[["5\n1 2 20\n2 3 12\n2 4 1\n4 5 3\n26 9\n1 10\n500 2\n2 30","206 321 542 328"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}