Black Cats Deployment

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 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. For 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: * Let $X=0$. * For each integer $j$ between $1$ and $N$ (inclusive) except $i$, do the following: * Add $c$ to $X$, where $c$ is the smallest joyfulness of an edge on the path from Vertex $i$ to Vertex $j$. * The niceness is the final value of $X$. ## Constraints * $1 \leq N \leq 10^{5}$ * $1 \leq a_i,b_i \leq N$ * $1 \leq c_i \leq 10^{9}$ * The given graph is a tree. * All input values are integers. ## Input Input is given from Standard Input in the following format: $N$ $a_1$ $b_1$ $c_1$ $:$ $a_{N-1}$ $b_{N-1}$ $c_{N-1}$ ## Partial Scores * In the test set worth $200$ points, $N \leq 1000$. * In the test set worth $200$ points, $c_i \leq 2$. [samples]