对于一名合格的公司职场人来说，「被压垮」是绝对不容许发生的事情。
无论是面对压力还是疲劳，都应该挺直腰杆，迎难而上！
除非…是被「它们」压倒在地。
「哎呀，不要着急！我只有两只手嘛！」
刚结束加班回到家中的少女，被一众毛茸茸的生物压倒在地。
它们或许并不能完全听懂她的话语，只顾着将圆圆的脑袋凑近她的手掌。
疲惫感从身体中逐渐消失，取而代之的是抚顺毛发带来的温暖舒展。

托帕养了 n 只毛茸茸的宠物，在休息时间，打算和他们玩数局游戏。
每局游戏，托帕可以任意选择至少一只宠物进行游戏，其他未被选择的宠物在休息。
其中 1 号宠物十分活泼，每局游戏都要参加。 n 号宠物比较慵懒，一直在睡觉，每局游戏都不参加。

另外，宠物之间有一些伙伴关系。如果两个互为伙伴关系的宠物中，恰好只有一只宠物参加游戏的总时长不能超过一定值。
具体而言，有 m 个伙伴关系，每个伙伴关系有三个参数 x,y,z ，表示 x 号宠物和 y 号宠物中恰好只有一只宠物在聚会中的总时间不能超过 z 。

请你帮托帕安排下每局游戏的参与者，使得总游戏时长最大。
如果游戏总时长可以无限大，则输出 inf 。
托帕并不想举行很多局游戏，总游戏局数不能超过 n^2 。

第一行包含两个正整数 n,m (1≤n≤100, 0≤m≤n*(n-1)/2) ，表示宠物数和伙伴关系数。
接下来 m 行，每行包含三个整数 x,y,z(1≤x<y≤n, 0≤z≤10^9) ，表示 x 号宠物和 y 号宠物中恰好只有一只宠物在聚会中的总时间不能超过 z 。
保证伙伴关系不重复。

如果总游戏时长可以无限大，则输出 inf 。
否则，第一行输出两个整数 T (0≤k≤10^18) 和 k (0≤k≤n^2) ，表示最大总游戏时长和游戏局数。
接下来 k 行，每行表示一局游戏，包含一个长度为 n 的01字符串 s 和一个整数 t ，表示一局游戏的参加者和这局游戏时长。若 i 号宠物参加，则 s[i]='1' ，否则 s[i]='0' 。
可以证明总游戏时长有限的情况下，不会超过 10^18 。
如果有多组方案，输出任意一种即可。

样例1：
5 4
1 3 2
1 4 2
2 3 1
2 5 1

样例2：
3 0

样例1：
4 4
10000 1
10010 1
10100 1
11110 1

样例2：
inf