Tenzing 有 $$$n$$$ 动物朋友。他将它们编号为从 $$$1$$$ 到 $$$n$$$。
有一天,丹增想和他的动物朋友们一起玩。为此,丹增将举办多场比赛。
在一场游戏中,他将选择一个集合 $$$S$$$,它是 $$$\{1,2,3,...,n\}$$$ 的子集,并选择一个整数 $$$t$$$。然后,他将在 $$$S$$$ 中与动物一起玩 $$$t$$$ 分钟的游戏。
但有一些限制:
1. Tenzing非常喜欢朋友$$$1$$$,所以$$$1$$$一定是$$$S$$$的元素。
2. Tenzing 不喜欢朋友 $$$n$$$,所以 $$$n$$$ 不能是 $$$S$$$ 的元素。
3. 还有 m 个附加限制。第 $$$i$$$ 个特殊限制由整数 $$$u_i$$$、$$$v_i$$$ 和 $$$y_i$$$ 描述,假设 $$$x$$$ 是 $$$u_i$$$ 和 $$$v_i$$$ 之一正在玩 Tenzing 的总时间。 Tenzing 必须确保 $$$x$$$ 小于或等于 $$$y_i$$$。否则,就会有不幸福的事。
Tenzing 想知道他可以和动物朋友一起玩的最大总时间。请找出丹增可以与他的动物朋友一起玩的最大总时间以及组织达到该最大总时间的游戏的方法,或者报告他可以与他的动物朋友一起玩无限长的时间。而且,丹增不想举办那么多比赛,所以他最多会举办$$$n^2$$$场比赛。
输入
输入的第一行包含两个整数 $$$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<v_i\leq n$$$, $$$0\leq y_i\leq 10^9$$$) — 描述第 $$$i$$$ 个特殊限制。保证对于 $$$1 \leq i < j \leq m$$$,$$$(u_i,v_i) \neq (u_j,v_j)$$$。
输出
如果Tenzing可以无限期地与他的动物朋友玩耍,则输出“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$$$。
在这个问题的约束下,可以证明,如果Tenzing只能和他的朋友一起玩有限的时间,那么他最多只能和他们一起玩$$$10^{18}$$$分钟。
示例
输入 #1
5 4 1 3 2 1 4 2 2 3 1 2 5 1
输出 #1
4 4 10000 1 10010 1 10100 1 11110 1
输入 #2
3 0
输出 #2
inf
注意
在第一个测试用例中:
1. Tenzing 将与好友 $$$\{1\}$$$ 举办一场游戏,时长 $$$1$$$ 分钟。
2. Tenzing 将与好友 $$$\{1,4\}$$$ 举办一场游戏,时长 $$$1$$$ 分钟。
3. Tenzing 将与好友 $$$\{1,3\}$$$ 举办一场游戏,时长 $$$1$$$ 分钟。
4. Tenzing 将与好友 $$$\{1,2,3,4\}$$$ 举办一场游戏,持续 $$$1$$$ 分钟。
如果在那之后,Tenzing 与朋友 $$$\{1,2\}$$$ 举办另一场比赛 $$$1$$$ 分钟。那么恰好其中一个朋友 $$$2$$$ 或 $$$3$$$ 与 Tenzing 的时间将变为 $$$2$$$ 分钟,这将不满足 $$$3$$$-rd 特殊限制。
在第二个测试用例中,没有特殊限制。因此,Tenzing 可以与好友 $$$\{1\}$$$ 无限期地举办游戏。