{"problem":{"name":"Black Cats Deployment","description":{"content":"Snuke Festival 2017 will be held in a tree with $N$ vertices numbered $1,2, ...,N$. The $i$\\-th edge connects Vertex $a_i$ and $b_i$, and has _joyfulness_ $c_i$. The staff is Snuke and $N-1$ black cat","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"asaporo2_e"},"statements":[{"statement_type":"Markdown","content":"Snuke Festival 2017 will be held in a tree with $N$ vertices numbered $1,2, ...,N$. The $i$\\-th edge connects Vertex $a_i$ and $b_i$, and has _joyfulness_ $c_i$.\nThe staff is Snuke and $N-1$ black cats. Snuke will set up the headquarters in some vertex, and from there he will deploy a cat to each of the other $N-1$ vertices.\nFor each vertex, calculate the _niceness_ when the headquarters are set up in that vertex. The niceness when the headquarters are set up in Vertex $i$ is calculated as follows:\n\n*   Let $X=0$.\n*   For each integer $j$ between $1$ and $N$ (inclusive) except $i$, do the following:\n    *   Add $c$ to $X$, where $c$ is the smallest joyfulness of an edge on the path from Vertex $i$ to Vertex $j$.\n*   The niceness is the final value of $X$.\n\n## Constraints\n\n*   $1 \\leq N \\leq 10^{5}$\n*   $1 \\leq a_i,b_i \\leq N$\n*   $1 \\leq c_i \\leq 10^{9}$\n*   The given graph is a tree.\n*   All input values are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$a_1$ $b_1$ $c_1$\n$:$\n$a_{N-1}$ $b_{N-1}$ $c_{N-1}$\n\n## Partial Scores\n\n*   In the test set worth $200$ points, $N \\leq 1000$.\n*   In the test set worth $200$ points, $c_i \\leq 2$.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"asaporo2_e","tags":[],"sample_group":[["3\n1 2 10\n2 3 20","20\n30\n30\n\n*   The figure below shows the case when headquarters are set up in each of the vertices $1$, $2$ and $3$.\n*   The number on top of an edge denotes the joyfulness of the edge, and the number below an vertex denotes the smallest joyfulness of an edge on the path from the headquarters to that vertex.\n\n![image](https://atcoder.jp/img/asaporo2/1ee10aa2a1bf5e43e05161f37d88bdc1.png)"],["15\n6 3 2\n13 3 1\n1 13 2\n7 1 2\n8 1 1\n2 8 2\n2 12 2\n5 2 2\n2 11 2\n10 2 2\n10 9 1\n9 14 2\n4 14 1\n11 15 2","16\n20\n15\n14\n20\n15\n16\n20\n15\n20\n20\n20\n16\n15\n20"],["19\n19 14 48\n11 19 23\n17 14 30\n7 11 15\n2 19 15\n2 18 21\n19 10 43\n12 11 25\n3 11 4\n5 19 50\n4 11 19\n9 12 29\n14 13 3\n14 6 12\n14 15 14\n5 1 6\n8 18 13\n7 16 14","103\n237\n71\n263\n370\n193\n231\n207\n299\n358\n295\n299\n54\n368\n220\n220\n319\n237\n370"]],"created_at":"2026-03-03 11:01:14"}}