{"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\u003cspan class\u003d\"tex-font-style-it\"\u003eThe original title of this problem is \"Tree Product Metric Voronoi Diagram Query Without One Point\".\u003c/span\u003e\u003c/p\u003e\u003cp\u003eYou are given two weighted trees $$$T_1,\\ T_2$$$ of size $$$N$$$, where each vertex are labeled with numbers $$$1 \\ldots N$$$. Let $$$dist(T_1,\\ i,\\ j)$$$ be the total weight of the shortest path from node $$$i$$$ to $$$j$$$ in tree $$$T_1$$$, and define $$$dist(T_2,\\ i,\\ j)$$$ similarly. \u003c/p\u003e\u003cp\u003eConsider a point set of size $$$N$$$. Similar to Manhattan metric (in fact, this is a generalization of it), we can define the distance between two points $$$1 \\le i,\\ j \\le N$$$: It is the sum of two distances, $$$dist(T_1,\\ i,\\ j) + dist(T_2,\\ i,\\ j)$$$. For each $$$1 \\le i \\le N$$$, please determine the \"closest point\" from the point $$$i$$$. Formally, for each $$$i$$$, you should find $$$min_{j \\neq i}{dist(T_1,\\ i,\\ j) + dist(T_2,\\ i,\\ j)}$$$. \u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eIn the first line, a single integer $$$N$$$ denoting the number of vertices in both trees is given. ($$$2 \\le N \\le 250\\,000$$$)\u003c/p\u003e\u003cp\u003eIn the next $$$N-1$$$ lines, description of the first tree is given. Each of the $$$N-1$$$ lines contains three integers $$$S_i, E_i, W_i$$$, which indicates there is an edge connecting two vertices $$$S_i, E_i$$$ with weight $$$W_i$$$ ($$$1 \\le S_i, E_i \\le N, 1 \\le W_i \\le 10^9$$$)\u003c/p\u003e\u003cp\u003eIn the next $$$N-1$$$ lines, description of the second tree is given in the same format.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint $$$N$$$ lines containing a single integer. In the $$$i$$$-th line, you should print a single integer denoting the answer for the point $$$i$$$.\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 10\n2 4 20\n3 4 30\n4 5 50\n1 2 15\n1 3 25\n1 4 35\n1 5 25\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e25\n25\n85\n65\n105\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","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\u003e9\n5 7 6577\n4 5 8869\n5 9 9088\n2 1 124\n6 2 410\n2 8 8154\n4 8 4810\n3 4 4268\n3 9 763\n6 2 8959\n7 4 7984\n3 8 504\n8 6 9085\n5 2 4861\n1 9 8539\n1 7 7834\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e18084\n9369\n9582\n23430\n26694\n9369\n23430\n9582\n22988\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}