## LCC '21 Contest 3 S3 - Roundabout

View as PDF

Points: 10 (partial)
Time limit: 4.0s
Java 8 10.0s
Memory limit: 256M

Author:
Problem type

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 .

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