The Matrix can be regarded as an enormous connected weighted graph. To describe the Matrix, you are given connected weighted graphs . The graphs will not contain self loops or duplicate edges. The Matrix is the graph where . That is, any vertex in can be described as a tuple where for .

For two vertices and in the Matrix, there is an edge between the vertices if and only if there exists an such that is in and for all we have that . As there is no self loops in the graphs it is obvious that such will be unique. The weight of the edge will be the weight of the edge is in .

You are required to output weight of the minimum spanning tree of . As the weight could be very large, you are only required to output modulo .

The first line of the input contains one integer  ().
Then the description of the  graphs follows. For each graph, the first line contains two integers  (). The -th of the following  lines contains three integers  (), indicating an edge of the graph. 
The sum of  and  over all graphs will be no greater than , respectively.

Output one integer, the answer.

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

10

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

14