Funny Tree (Extreme Version)

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.

Input

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

Output the length of the longest path!

Subtask 1 (18 points): 0 ≤ w ≤ 0
Subtask 2 (21 points): 0 ≤ w ≤ 1
Subtask 3 (26 points): 0 ≤ w ≤ min(N, 30)
Subtask 4 (35 points): 0 ≤ w ≤ N
Subtask 5 (0 points): Sample testcases

Sample 1

Input:
5
1 2 0
2 3 0
3 4 0
4 5 1
Output:
6
Explanation: {4,5,3,2,1}

Input:
10
2 1 1
3 1 1
1 4 0
5 1 2
6 4 1
2 7 2
8 4 2
8 9 3
6 10 0
Output:
42

Source

Well, orange really needed a stopper, and if this russian contest ex version can't stop someone then please let them claim their NOI first thanks :)

Submitting .cpp to 'Funny Tree (Extreme Version)'

Time Limit: 1 Seconds
Memory Limit: 512MB
No. of ACs: 8
Your best score: 0
Source: RuCode 2020 Div A (Extreme Version) (0rang3, rs)
Editorial: 1