Problem E
Bartering

We have all heard the fascinating story of how someone managed to trade a paperclip for a pen, then traded the pen for a door handle, and so on, until they eventually traded their way to a house. In today’s housing market, you think this sounds like a brilliant idea and decide to try something similar.

After analyzing the market, you realize that there are $N$ distinct items and $M$ possible trades. A trade consists of a set of items that you can exchange for exactly one other item. For example, a trade could be 2 apples and 3 pears for an orange. Formally, a trade can be described as

Here, $C_{i,j}$ is the coefficient for $F_j$ in trade $i$. This means that $C_{i,j}$ is the number of $F_j$ required for the trade. $r_i$ is the item you receive as a result of trade $i$. Note that not all items need to be part of a particular trade; for these items, $C_{i,j} = 0$.

Each trade can be performed any number of times. Your goal is to calculate how many paperclips are needed to acquire a house.

The item $F_0$ represents the paperclip, and the item $F_{N-1}$ represents the house.

Input

The first line contains two integers $N$ and $M$ ($2 \leq N \leq 10^5$, $1 \leq M \leq 10^5$), the number of items and the number of trades.

Next, the $M$ trades are described. Each description begins with two integers $r_i$ ($0 \leq r_i < N$) and $k_i$ ($1 \leq k_i \leq N$), where $r_i$ is the item you receive from trade $i$, and $k_i$ is the number of distinct items used in the trade. Then follow $k_i$ lines, each containing two integers $C_{i,j}$ ($1 \leq C_{i,j} \leq 100$) and $j$ ($0 \leq j < N$), which indicate that the coefficient $C_{i,j}$ belongs to item $F_j$ in the trade. Note that items with coefficient $0$ are not included in the input.

Let $K$ be the sum of all $k_i$ values across all trades. It holds that $K \leq 10^5$.

It is guaranteed that all items can be obtained by starting with a paperclip, and you can purchase each item for at most $10^9$ paperclips each.

Output

Print a single integer: the minimum number of paperclips required to trade your way to a house.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

4 4
1 1
5 1
2 1
2 0
1 2
2 0
1 2
3 2
1 1
1 2

6

3 2
1 1
7 0
2 1
8 1

56