Задача F. (20081222) Разрезы ≡

Условие

Рассмотрим ориентированный взвешенный граф G = (V,E) с двумя выделенными вершинами s и t. Веса всех ребер — натуральные числа. Назовем s − t разрезом пару множеств вершин S и T такую, что выполняются следующие условия:

• S ∪ T = V,
• S ∩ T = ∅,
• s ∈ S, t ∈ T.

Назовем величиной разреза (S,T) суммарный вес ребер, которые направлены из S в T. Упорядочим все s − t разрезы G по неубыванию величины. Вам нужно вывести первые k разрезов в этом порядке.

Формат входного файла

В первой строке записаны два натуральных числа n и m — количество вершин и ребер в графе (1 ≤ n ≤ 50, 1 ≤ m ≤ 300). В следующих m строках находятся описания ребер — три натуральных числа a, b и c, которые задают ребро, идущее из вершины a в вершину b с весом c (1 ≤ a, b ≤ n, 1 ≤ c ≤ 10⁹). Гарантируется, что в графе нет кратных ребер и петель (однако могут быть два ребра, направленные друг навстречу другу). Последняя строка содержит одно натуральное число k — количество разрезов, которые необходимо вывести (1 ≤ k ≤ 300, k не превосходит общее количество разрезов в графе).

Вершины s и t имеют номера 1 и n соответственно.

Формат выходного файла

Выведите искомые k разрезов по одному на строке. Разрез задается строкой, состоящей из n символов. i-й символ равен нулю, если вершина с номером i лежит в S, в противном случае i-й символ должен равняться единице. Если несколько разрезов имеют одинаковую величину, то вы можете вывести их в любом порядке.

Примеры тестов

6 6
1 2 1
2 3 2
2 4 3
3 5 3
4 5 2
5 6 1
16

011111
000001
011001
011101
010101
010001
011011
001001
000101
001011
010111
001111
000011
010011
000111
001101