Neru has a connected graph with ~N~ nodes numbered from ~1~ to ~N~. The nodes are connected by a network of ~N~ bidirectional edges. The graph has no duplicate edges.

He defines a roundabout walk as the shortest traversal from a node to itself, where during the traversal, the same edge cannot be used twice in a row. This means that the move from node ~b~ to node ~a~ isn't possible if the previous move was from node ~a~ to node ~b~.

He asks you to sum up the length of the roundabout walks for every node in the graph and output the answer modulo ~10^{9}+7~.

Note: In a roundabout walk, he can use the same edge twice, but not twice in a row.

Input Specification

The first line of input contains an integer, ~N (3 \le N \le 10^{6})~.

Each of the next ~N~ lines contains three space-separated integers, ~a_i (1 \le a_i \le N)~, ~b_i (1 \le b_i \le N)~, and ~c_i (1 \le c_i \le 10^{6})~, representing a bidirectional connection between node ~a_i~ and node ~b_i~ with length ~c_i~. The graph has no duplicate edges and ~a_i \neq b_i~.

Output Specification

Output a single integer, the sum of all roundabout walks, modulo ~10^{9}+7~.

Subtasks

Subtask 1 [15%]

~(3 \le N \le 10^{3})~

Subtask 2 [85%]

~(3 \le N \le 10^{6})~

Sample Input 1

4
1 2 2
2 3 3
3 1 1
1 4 1

Sample Output 1

26

Explanation

The length of the roundabout walks starting from nodes ~1~, ~2~, and ~3~ is ~6~. The length of the roundabout walk starting from node ~4~ is ~8~. Therefore, the sum of the roundabout walks is ~6+6+6+8=26~.