{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e从前,在美丽的摩尔达维亚领土上有$$$N$$$个中世纪小镇,它们被独一无二地编号从$$$1$$$到$$$N$$$。编号为$$$1$$$的小镇是首都。这些小镇之间由$$$N-1$$$条双向道路相连,每条道路的长度以公里表示。任意两个小镇之间都有一条独一无二的路径,可以在不经过同一个小镇两次的情况下到达(即道路构成的图是一棵树)。\u003c/p\u003e\u003cp\u003e当一座小镇受到攻击时,情况必须尽快报告给首都。消息由使者传递,每座小镇都有一名使者。每位使者都有启程所需时间和启程后的恒定速度(以分钟每公里表示)。 \u003c/p\u003e\u003cp\u003e从一座小镇发出的消息总是沿着到首都的最短路径传递。最初,被攻击的小镇的使者传递消息。在每座他经过的小镇,使者有两个选择:要么继续前往下一座朝着首都的小镇,要么将消息交给这座小镇的使者。新的使者也采用上述相同的算法。总的来说,消息在到达首都之前可能由任意数量的使者传递。\u003c/p\u003e\u003cp\u003e你的任务是找出每座小镇发送消息到首都所需的最短时间。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e输入的第一行包含一个整数$$$N$$$,表示摩尔达维亚的小镇数量。接下来的$$$N-1$$$行中,每行包含三个整数$$$u$$$ $$$v$$$ $$$d$$$,用一个空格分隔,描述了一条长度为$$$d$$$公里的道路,连接了编号为$$$u$$$和$$$v$$$的小镇。\u003c/p\u003e\u003cp\u003e随后是$$$N-1$$$对整数,每行一个。第$$$i$$$对整数,$$$S_i$$$ $$$V_i$$$描述了第$$$(i+1)$$$座小镇的使者的特征:准备旅程需要的分钟数$$$S_i$$$,以及每公里旅行所需的分钟数$$$V_i$$$。首都没有使者。\u003c/p\u003e\u003cul\u003e \u003cli\u003e $$$3 \\leq N \\leq 10^5$$$。 \u003c/li\u003e\u003cli\u003e $$$0 \\leq S_i \\leq 10^9$$$。 \u003c/li\u003e\u003cli\u003e $$$1 \\leq V_i \\leq 10^9$$$。 \u003c/li\u003e\u003cli\u003e 每条道路的长度为非负数,且不超过$$$10^4$$$。 \u003c/li\u003e\u003c/ul\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e输出应当包含一行,包含$$$N-1$$$个整数。第$$$i$$$个数字表示从第$$$(i +1)$$$座小镇发送消息到首都所需的最短时间,以分钟计算。\u003c/p\u003e"}},{"title":"示例 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\n1 2 20\n2 3 12\n2 4 1\n4 5 3\n26 9\n1 10\n500 2\n2 30\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e206 321 542 328 \u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003eCEOI 2009\u003c/p\u003e"}}]}