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!

Subtasks

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}

Sample 2

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 to 'Funny Tree (Extreme Version)'


You're not logged in! Click here to login


Submitting to 'Funny Tree (Extreme Version)'


You're not logged in! Click here to login


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


You're not logged in! Click here to login


Compile Errors


							
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

Subtask Score
1 18
2 21
3 26
4 35
5 0