D. Тенцинг и его друзья животные
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Расскажи историю обо мне и моих друзьях животных.

У Тенцинга есть $$$n$$$ друзей животных. Он пронумеровал их от $$$1$$$ до $$$n$$$.

Однажды Тенцинг захотел поиграть со своими друзьями. Для этого Тенцинг устроит несколько игр.

В рамках одной игры он выберет множество $$$S$$$, которое является подмножеством $$$\{1,2,3,...,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$$$ меньше или равно $$$y_i$$$. Иначе будет несчастье.

Тенцинг хочет узнать максимальное общее время, которое он может играть со своими друзьями животными. Пожалуйста, найдите максимальное общее время, которое Тенцинг может играть со своими друзьями животными, и способ организации игр, при котором достигается это максимальное общее время, или сообщите, что он может играть со своими друзьями животными бесконечное количество времени. Кроме того, Тенцинг не хочет устраивать очень много игр, поэтому он устроит не более $$$n^2$$$ игр.

Входные данные

Первая строка входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \leq n \leq 100$$$, $$$0 \leq m \leq \frac{n(n-1)}{2}$$$) — количество друзей животных и количество специальных ограничений.

В $$$i$$$-й из следующих $$$m$$$ строк ввода содержится три целых числа $$$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)$$$.

Выходные данные

Если Тенцинг может играть со своими друзьями-животными бесконечное количество времени, выведите «inf» (без кавычек).

Иначе, в первой строке выведите общее время $$$T$$$ ($$$0 \leq t \leq 10^{18}$$$) и количество игр $$$k$$$ ($$$0 \leq k \leq n^2$$$).

В следующих $$$k$$$ строках вывода выведите двоичную строку $$$s$$$ длины $$$n$$$ и целое число $$$t$$$ ($$$0 \leq t \leq 10^{18}$$$) — представление множества $$$S$$$ и количество минут, в течение которых будет играться эта игра. Если $$$s_i=\texttt{1}$$$, то $$$i \in S$$$, иначе, если $$$s_i=\texttt{0}$$$, то $$$i \notin S$$$.

При ограничениях этой задачи можно доказать, что если Тенцинг может играть со своими друзьями только конечное количество времени, то он может играть с ними не более $$$10^{18}$$$ минут.

Примеры
Входные данные
5 4
1 3 2
1 4 2
2 3 1
2 5 1
Выходные данные
4 4
10000 1
10010 1
10100 1
11110 1
Входные данные
3 0
Выходные данные
inf
Примечание

В первом примере:

  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\}$$$ в течение бесконечного количества времени.