Orange is trying to find a permutation of nodes to represent a path around a tree. The tree has N nodes, and each edge has a weight.
Let d(u,v) be the maximum of the edge weights of the edges between nodes u and v.
Orange wants a long holiday to escape from his very annoying friends who try to read his whatsapp. Help him find the time it takes him to travel around the tree, formally the maximum value of Σ 2d(pi,pi-1) across all permutations of vertices p1,p2,...,pN. (Note that Σ refers to the summation symbol)
As this number could be large, output the result modulo 109+7.
First line contains 1 integer (2 ≤ N ≤ 100000)
Each of the next N-1 lines contains 3 integers u (1 ≤ u ≤ N), v (1 ≤ v ≤ N) and w (0 ≤ w ≤ N), representing an edge from node u to node v weight w.
Output the length of the longest path!