Money Copying

The GIST House secondhand market runs events that exchange money for a specific item, or one specific item for another specific item. When items are swapped, extra money may also change hands. The market has unlimited money and items, so any trade can be repeated indefinitely as long as goods remain. However, a customer can hold at most one item at a time.

For example, suppose the following trades exist:

• $t_1$: A user buys item $1$ for $10$ won.
• $t_2$: A user adds $10$ won and trades it for item $2$.
• $t_3$: A user sells item $2$ and receives $21$ won.
• $t_4$: A user trades item $2$ for item $1$ and receives an additional $12$ won.
• $t_5$: A user buys item $2$ for $7$ won.

Suppose the development team allows only the trades in the list $L_1 = \{t_1, t_2, t_3\}$. Then choosing $t_1, t_2, t_3$ in this order turns $20$ won into $21$ won. Repeating this indefinitely lets the money grow without bound. Copied money can harm the national economy, so the development team wants to prevent this. Given a list of trades, the team wants to determine whether the list is safe.

The safety level of a list is defined as follows.

• If a person starts with $C$ won and can grow their money without bound by repeating trades, the safety level of the list is the minimum value of $C$. If no such $C$ exists, the safety level is $\infty$. To grow the money, it is not necessary to sell every item.

For example, the safety level of $L_1 = \{t_1, t_2, t_3\}$ is $20$, because starting with $20$ won and repeating $t_1, t_2, t_3$ in order works. However, a person with $19$ won cannot grow their money without bound no matter what they do. The safety level of $L_2 = \{t_3, t_4, t_5\}$ is $7$.

Meanwhile, the safety level of $L_3 = \{t_2, t_3, t_4\}$ is $\infty$. It seems that repeating $t_2$ and $t_4$ would grow the money without bound, but there is no way to obtain item $1$ or item $2$, so those trades cannot be attempted.

Write a program that, given a list of barter trades, measures the safety level of that list.

The first line contains the number of items $N$ and the length of the barter trade list $M$. ($1 \leq N \leq 1\,000, 1 \leq M \leq \min\left(N^2+N, 3\,000\right)$)

From the second line, the next $M$ lines each give one piece of information about the trade list $L$ in one of the following five formats.

• $1\ c\ i$: You can buy item $i$ for $c$ won.
• $2\ i\ c$: You can sell item $i$ and earn $c$ won.
• $3\ i_1\ i_2$: You can trade item $i_1$ for item $i_2$.
• $4\ i_1\ c\ i_2$: You can exchange item $i_1$ and $c$ won for item $i_2$.
• $5\ i_1\ i_2\ c$: You can exchange item $i_1$ for item $i_2$ and $c$ won.

$i$, $i_1$, and $i_2$ are integers from $1$ to $N$. $c$ is an integer from $1$ to $1\,000$. The values on each line are separated by spaces.

In the trade list $L$, formats $3$, $4$, and $5$ each satisfy $i_1 \neq i_2$.

No two lines of format $1$ share the same $i$.

No two lines of format $2$ share the same $i$.

No two lines of formats $3$, $4$, or $5$ share both the same $i_1$ and $i_2$. For example, 3 1 2 and 4 1 1 2 are never given together. However, 3 1 2 and 3 1 3 can be given together, because they share $i_1$ but not $i_2$.

Trades are not reversible. For example, the input 3 1 2 does not mean you can trade item $2$ for item $1$.

Print the safety level of the list. If the safety level is $\infty$, print the string INF.