Kingdom

Background

JSOI is a kingdom with highly developed technology. Recently, the emergence of teleportation technology has greatly facilitated people's travel. King JS has entrusted the task of evaluating the kingdom's transportation system to the Minister of Transport, JYY.

Description

The JSOI kingdom consists of $N$ cities connected by teleportation tunnels. To prevent infinite teleportation loops, there is one and only one path between any two cities consisting of teleportation tunnels. The $i$-th tunnel connects cities $u_i$ and $v_i$ and takes $t_i$ time to traverse.

Inside the $i$-th city, there are $m_i$ nodes, consisting of $m_i-1$ residential nodes surrounding one teleportation node. Let us label the outer residential nodes from $1$ to $m_i-1$. There is a bidirectional road of length $l_{ij}$ between the $j$-th residential node and the next numbered residential node (the $(m_i-1)$-th node is adjacent to the $1$-st node, forming a residential ring). Each residential node also has a bidirectional road to the teleportation node with length $c_{ij}$.

For two residential nodes within the same city, they can reach each other by passing through other nodes in the city (they may pass through the city's teleportation node, but cannot use the teleportation node to teleport to other cities). For two residential nodes belonging to different cities, one must first reach the teleportation node of the starting city, travel through a series of teleportation tunnels to reach the teleportation node of the destination city, and then travel through the roads within that city to reach the destination.

Now, the Minister of Transport, JYY, wants to calculate the sum of the lengths of the shortest paths between all pairs of residential nodes. Since this number can be very large, you only need to output the result modulo $10^9+7$.

Input

The first line contains an integer $N$, representing the total number of cities in JSOI.

The next $N-1$ lines each contain three integers $u_i, v_i, t_i$, representing a teleportation tunnel between city $u_i$ and city $v_i$ with a travel time of $t_i$.

The next $3N$ lines describe the node information within each city, with 3 lines per city: The first line contains an integer $m_i$, the number of nodes inside the $i$-th city. The second line contains $m_i-1$ integers $l_{ij}$, the lengths of the roads between the $j$-th residential node and the next residential node in the $i$-th city. * The third line contains $m_i-1$ integers $c_{ij}$, the lengths of the roads between the $j$-th residential node and the teleportation node of the $i$-th city.

Output

Output a single integer representing the sum of the lengths of the shortest paths between all pairs of residential nodes, modulo $10^9+7$.

Examples

Input 1

3
1 2 50
2 3 59
4
24 41 93
10 66 43
4
88 28 41
4 30 13
5
4 10 61 100
70 58 34 79

Output 1

10132

Constraints

• For $20\%$ of the data: $0 < \sum (m_i - 1) \le 100$.
• For another $20\%$ of the data: $m_i = 3$.
• For another $10\%$ of the data: $N = 1$.
• For $100\%$ of the data: $1 \le N \le 10^5$, $m_i \ge 3$, $0 < \sum (m_i - 1) \le 5 \times 10^5$, $0 < t_i, l_{ij}, c_{ij} \le 10^9$.