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