{"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\u003eOnce upon a time, there were $$$N$$$ medieval towns in the beautiful Moldavian territory, uniquely numbered from $$$1$$$ through $$$N$$$. The town numbered with $$$1$$$ was the capital city. The towns were connected by $$$N-1$$$ bidirectional roads, each road having a length expressed in kilometers. There was a unique way to travel between any pair of towns without going through a town twice (i.e. the graph of roads was a tree). \u003c/p\u003e\u003cp\u003eWhen a town was attacked, the situation had to be reported as soon as possible to the capital. The message was carried by harbingers, one of which resided in each town. Each harbinger was characterized by the amount of time required to start the journey and by his constant speed (expressed in minutes per kilometer) after departure. \u003c/p\u003e\u003cp\u003eThe message from a town was always carried on the unique shortest path to the capital. Initially, the harbinger from the attacked town carried the message. In each town that he traversed, a harbinger had two options: either go to the next town towards the capital, or leave the message to the harbinger from this town. The new harbinger applied the same algorithm as above. Overall, a message could be carried by any number of harbingers before arriving in the capital. \u003c/p\u003e\u003cp\u003eYour task is to find, for each town, the minimum time required to send a message from that town to the capital. \u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of the input contains one integer $$$N$$$, the number of towns in Moldavia. Each of the following $$$N-1$$$ lines contains three integers $$$u$$$ $$$v$$$ $$$d$$$, separated by one space, describing a road of length $$$d$$$ kilometers between towns numbered with $$$u$$$ and $$$v$$$.\u003c/p\u003e\u003cp\u003eSubsequently, $$$N-1$$$ pairs of integers follow, one per line. The $$$i$$$-th pair, $$$S_i$$$ $$$V_i$$$ describes the characteristics of the harbinger in the $$$(i+1)$$$-th town: $$$S_i$$$ is the number of minutes to prepare for the journey, and $$$V_i$$$ is the number of minutes needed to travel one kilometer. There is no harbinger in the capital. \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 The length of each road is nonnegative and will not exceed $$$10^4$$$. \u003c/li\u003e\u003c/ul\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eThe output should consist of exactly one line containing $$$N-1$$$ integers. The $$$i$$$-th number represents the minimum time, in minutes, required to send a message from the $$$(i +1)$$$-th town to the capital. \u003c/p\u003e"}},{"title":"Examples","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\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eCEOI 2009\u003c/p\u003e"}}]}