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