CF1842D.Tenzing and His Animal Friends

Tell a story about me and my animal friends.

Tenzing has $n$ animal friends. He numbers them from $1$ to $n$.

One day Tenzing wants to play with his animal friends. To do so, Tenzing will host several games.

In one game, he will choose a set $S$ which is a subset of ${1,2,3,...,n}$ and choose an integer $t$. Then, he will play the game with the animals in $S$ for $t$ minutes.

But there are some restrictions:

1. Tenzing loves friend $1$ very much, so $1$ must be an element of $S$.
2. Tenzing doesn't like friend $n$, so $n$ must not be an element of $S$.
3. There are m additional restrictions. The $i$-th special restriction is described by integers $u_i$, $v_i$ and $y_i$, suppose $x$ is the total time that exactly one of $u_i$ and $v_i$ is playing with Tenzing. Tenzing must ensure that $x$ is less or equal to $y_i$. Otherwise, there will be unhappiness.

Tenzing wants to know the maximum total time that he can play with his animal friends. Please find out the maximum total time that Tenzing can play with his animal friends and a way to organize the games that achieves this maximum total time, or report that he can play with his animal friends for an infinite amount of time. Also, Tenzing does not want to host so many games, so he will host at most $n^2$ games.

给我和我的动物朋友们讲一个故事。

丹增有 $n$ 个动物朋友，他将它们编号为 $1$ 到 $n$。

一天，丹增想和他的动物朋友们一起玩耍。为此，他将举办若干场游戏。

在一场游戏中，他将选择一个集合 $S$，它是 $\{1,2,3,\dots,n\}$ 的一个子集，并选择一个整数 $t$；然后，他将与集合 $S$ 中的动物们一起玩 $t$ 分钟。

但存在一些限制条件：

1. 丹增非常喜爱朋友 $1$，因此 $1$ 必须属于 $S$；
2. 丹增不喜欢朋友 $n$，因此 $n$ 一定不能属于 $S$；
3. 还有 $m$ 条额外的限制条件。第 $i$ 条特殊限制由三个整数 $u_i$、$v_i$ 和 $y_i$ 描述：设 $x$ 表示恰好 $u_i$ 和 $v_i$ 中的一个参与了丹增所举办的全部游戏的总时长，则丹增必须保证 $x \le y_i$；否则将产生不愉快。

丹增想知道：他最多能和动物朋友们共度多少总时间？请找出该最大总时间，以及一种达到该最大总时间的游戏组织方案；或者判断他可以与动物朋友们无限时长地玩耍。此外，丹增不想举办过多游戏，因此他举办的总游戏场数至多为 $n^2$ 场。

The first line of input contains two integers $n$ and $m$ ($2 \leq n \leq 100$, $0 \leq m \leq \frac{n(n-1)}{2}$) — the number of animal friends and the number of special restrictions.

The $i$-th of the following $m$ lines of input contains three integers $u_i$, $v_i$ and $y_i$ ($1\leq u_i \lt v_i\leq n$, $0\leq y_i\leq 10^9$) — describing the $i$-th special restriction. It is guaranteed that for $1 \leq i \lt j \leq m$, $(u_i,v_i) \neq (u_j,v_j)$.

输入的第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 100$，$0 \leq m \leq \frac{n(n-1)}{2}$）——分别表示动物朋友的数量和特殊限制的数量。

接下来的 $m$ 行中，第 $i$ 行包含三个整数 $u_i$、$v_i$ 和 $y_i$（$1\leq u_i \lt v_i\leq n$，$0\leq y_i\leq 10^9$）——描述第 $i$ 个特殊限制。保证对任意 $1 \leq i \lt j \leq m$，均有 $(u_i,v_i) \neq (u_j,v_j)$。

If Tenzing can play with his animal friends for an infinite amount of time, output "inf". (Output without quotes.)

Otherwise, in the first line, output the total time $T$ ($0 \leq t \leq 10^{18}$) and the number of games $k$ ($0 \leq k \leq n^2$).

In the following $k$ lines of output, output a binary string $s$ of length $n$ and an integer $t$ ($0 \leq t \leq 10^{18}$) — representing the set $S$ and the number of minutes this game will be played. If $s_i=\texttt{1}$, then $i \in S$, otherwise if $s_i=\texttt{0}$, then $i \notin S$.

Under the constraints of this problem, it can be proven that if Tenzing can only play with his friends for a finite amount of time, then he can only play with them for at most $10^{18}$ minutes.

如果丹增可以与他的动物朋友们无限时长地玩耍，则输出 inf。（不带引号）

否则，在第一行中，输出总时间 $T$（$0 \leq T \leq 10^{18}$）和游戏场数 $k$（$0 \leq k \leq n^2$）。

接下来的 $k$ 行中，每行输出一个长度为 $n$ 的二进制字符串 $s$ 和一个整数 $t$（$0 \leq t \leq 10^{18}$），分别表示集合 $S$ 以及该局游戏将进行的分钟数。若 $s_i=\texttt{1}$，则 $i \in S$；若 $s_i=\texttt{0}$，则 $i \notin S$。

在本题约束下，可以证明：若丹增只能与朋友们玩耍有限的时间，则该总时长至多为 $10^{18}$ 分钟。

In the first test case:

1. Tenzing will host a game with friend ${1}$ for $1$ minute.
2. Tenzing will host a game with friends ${1,4}$ for $1$ minute.
3. Tenzing will host a game with friends ${1,3}$ for $1$ minute.
4. Tenzing will host a game with friends ${1,2,3,4}$ for $1$ minute.

If after that, Tenzing host another game with friends ${1,2}$ for $1$ minute. Then the time of exactly one of friends $2$ or $3$ with Tenzing will becomes $2$ minutes which will not satisfy the $3$-rd special restriction.

In the second test case, there is no special restrictions. So Tenzing can host a game with friend ${1}$ for an infinite amount of time.

在第一个测试用例中：

1. 登津将与朋友 ${1}$ 一起主持一局游戏，持续 $1$ 分钟。
2. 登津将与朋友 ${1,4}$ 一起主持一局游戏，持续 $1$ 分钟。
3. 登津将与朋友 ${1,3}$ 一起主持一局游戏，持续 $1$ 分钟。
4. 登津将与朋友 ${1,2,3,4}$ 一起主持一局游戏，持续 $1$ 分钟。

若此后登津再与朋友 ${1,2}$ 一起主持一局游戏，持续 $1$ 分钟，则朋友 $2$ 或 $3$ 中恰好有一人与登津共处的时间将变为 $2$ 分钟，这将违反第 $3$ 条特殊限制。

在第二个测试用例中，不存在任何特殊限制。因此登津可以与朋友 ${1}$ 无限长时间地主持一局游戏。