Задан ориентированный граф, каждое ребро которого обладает целочисленной пропускной способностью. Найдите максимальный поток из вершины с номером 1 в вершину с номером n и постройте декомпозицию этого потока.

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

Первая строка содержит количество вершин n и количество ребер m (2 ≤ n ≤ 500, 1 ≤ m ≤ 10000) графа. Следующие m строк содержат по три числа: номера вершин, которые соединяет соответствующее ребро графа и его пропускную способность. Пропускные способности не превосходят 109.

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

В первой строке выведите количество путей в декомпозиции максимального потока из вершины 1 в вершину n. Следующие строки должны содержать описания элементарых потоков, на который был разбит максимальный. Описание следует выводить в следующем формате: величина потока, количество ребер в пути, вдоль которого течет данный поток и номера ребер в этом пути. Ребра нумеруются с единицы в порядке появления во входных данных.