Decomposition of the Stream
Given a directed graph where each edge has an integer capacity, your task is to determine the maximum flow from vertex 1 to vertex n and provide a decomposition of this flow.
Input
The first line contains two integers: the number of vertices n and the number of edges m (2 ≤ n ≤ 500, 1 ≤ m ≤ 10000). The next m lines each contain three integers: the indices of the vertices connected by an edge and the capacity of that edge. Capacities do not exceed 10^9.
Output
On the first line, output the number of paths in the decomposition of the maximum flow from vertex 1 to vertex n. The subsequent lines should describe the elementary flows that make up the maximum flow. Each description should include: the magnitude of the flow, the number of edges in the path through which this flow travels, and the indices of the edges in this path. Edges are numbered starting from one, according to their order in the input data.