Задан ориентированный граф, каждое ребро которого обладает целочисленной пропускной способностью. Найдите максимальный поток из вершины с номером \textbf{1} в вершину с номером \textbf{n} и постройте декомпозицию этого потока. \InputFile Первая строка содержит количество вершин n и количество ребер m (\textbf{2} ≤ \textbf{n} ≤ \textbf{500}, \textbf{1} ≤ \textbf{m} ≤ \textbf{10000}) графа. Следующие \textbf{m} строк содержат по три числа: номера вершин, которые соединяет соответствующее ребро графа и его пропускную способность. Пропускные способности не превосходят \textbf{10^9}. \OutputFile В первую строку количество путей в декомпозиции максимального потока из вершины с номером \textbf{1} в вершину с номером \textbf{n}. Следующие строки должны содержать описания элементарых потоков, на который был разбит максимальный. Описание следует выводить в следующем формате: величина потока, количество ребер в пути, вдоль которого течет данный поток и номера ребер в этом пути. Ребра нумеруются с единицы в порядке появления во входных данных.