eolymp
bolt
Try our new interface for solving problems
Problems

Декомпозиция потока

Декомпозиция потока

Time limit 1 second
Memory limit 128 MiB

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

Input data

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

Output data

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

Examples

Input example #1
4 5
1 2 1
1 3 2
3 2 1
2 4 2
3 4 1
Output example #1
3
1 2 1 4
1 3 2 3 4
1 2 2 5