Neru has a connected graph with nodes numbered from to . The nodes are connected by a network of 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 to node isn't possible if the previous move was from node to node .

He asks you to sum up the length of the roundabout walks for every node in the graph and output the answer modulo .

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, .

Each of the next lines contains three space-separated integers, , , and , representing a bidirectional connection between node and node with length . The graph has no duplicate edges and .

#### Output Specification

Output a single integer, the sum of all roundabout walks, modulo .

#### Subtasks

##### Subtask 1 [15%]

##### Subtask 2 [85%]

#### 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 , , and is . The length of the roundabout walk starting from node is . Therefore, the sum of the roundabout walks is .

## Comments