{"raw_statement":[{"iden":"problem statement","content":"We have a tree with $N$ vertices numbered $1, 2, \\dots, N$.  \nThe $i$\\-th edge $(1 \\leq i \\leq N - 1)$ connects Vertex $u_i$ and Vertex $v_i$ and has a weight $w_i$.\nFor different vertices $u$ and $v$, let $f(u, v)$ be the greatest weight of an edge contained in the shortest path from Vertex $u$ to Vertex $v$.\nFind $\\displaystyle \\sum_{i = 1}^{N - 1} \\sum_{j = i + 1}^N f(i, j)$."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 10^5$\n*   $1 \\leq u_i, v_i \\leq N$\n*   $1 \\leq w_i \\leq 10^7$\n*   The given graph is a tree.\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$u_1$ $v_1$ $w_1$\n$\\vdots$\n$u_{N - 1}$ $v_{N - 1}$ $w_{N - 1}$"},{"iden":"sample input 1","content":"3\n1 2 10\n2 3 20"},{"iden":"sample output 1","content":"50\n\nWe have $f(1, 2) = 10$, $f(2, 3) = 20$, and $f(1, 3) = 20$, so we should print their sum, or $50$."},{"iden":"sample input 2","content":"5\n1 2 1\n2 3 2\n4 2 5\n3 5 14"},{"iden":"sample output 2","content":"76"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}