CF1842D Tenzing and His Animal Friends

Tenzing 有 $ n $ 个动物朋友。他把它们从 $ 1 $ 到 $ n $ 编号。 一天，Tenzing 想和他的动物朋友们玩游戏。为此，Tenzing 将组织一些游戏。 在一项游戏内，他将会选择一个是 $ \{1,2,3,...,n\} $ 的子集的集合 $ S $ 并选择一个整数 $ 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 想要知道他可以和动物朋友们玩的最长总时间。请找到 Tenzing 可以和动物朋友们玩的最长总时间和一种可以达到这个最大总时间的组织游戏方式，或报告他可以玩无限长的时间。此外，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

如果 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. Tenzing 将和朋友 $ \{1\} $ 举办游戏，持续 $ 1 $ 分钟。 2. Tenzing 将和朋友 $ \{1,4\} $ 举办游戏，持续 $ 1 $ 分钟。 3. Tenzing 将和朋友 $ \{1,3\} $ 举办游戏，持续 $ 1 $ 分钟。 4. Tenzing 将和朋友 $ \{1,2,3,4\} $ 举办游戏，持续 $ 1 $ 分钟。 如果在此之后，Tenzing 和朋友 $ \{1,2\}$ 举办另一场游戏，持续 $ 1 $ 分钟，则 Tenzing 恰和朋友 $ 2 $ 或 $ 3 $ 游玩的时间将变为 $ 2 $ 分钟。这不满足第 $ 3 $ 条特别限制。 对于第二组测试样例，不存在特别限制。所以 Tenzing 可以和朋友 $ \{1\} $ 玩时间无限长的游戏。