Заданий орієнтований граф, кожне ребро якого має цілу пропускну здатність.

Знайдіть максимальний потік із вершини з номером \(1\) у вершину з номером \(n\) і побудуйте декомпозицію цього потоку.

Формат вхідних даних

Перший рядок вхідного файлу містить \(n\) і \(m\) - кількість вершин та кількість ребер графа (\(2 \le n \le 500\), \(1 \le m \le 10\,000\)).

Наступні \(m\) рядків містять три числа: номери вершин, які з'єднує відповідне ребро графа та його пропускну спроможність. Пропускні можливості не перевищують \(10^9\).

Формат вихідних даних

У першому рядку вихідного файлу виведіть одне число - кількість шляхів декомпозації максимального потоку з вершини з номером \(1\) у вершину з номером \(n\).

Наступні рядки повинні містити опис елементарних потоків, на який був розбитий максимальний. Опис слід виводити в наступному форматі: величина потоку, кількість ребер у дорозі, вздовж якого тече цей потік і номери ребер на цьому шляху. Ребра нумеруються з одиниці у порядку появи у вхідному файлі.

Приклад вхідних даних

4 5
1 2 1
1 3 2
3 2 1
2 4 2
3 4 1

Приклад вихідних даних

3
1 2 1 4
1 3 2 3 4
1 2 2 5