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

#ifdef ONPC
    # define _GLIBCXX_DEBUG
    #define deb(a) cerr << "========" << #a << " = " << a << endl;
#else
    #define deb(a)
#endif
#define sz(a) (int)(a).size()


#include <bits/stdc++.h>

using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;

struct Edge
{
    int from, to, c, f;
    Edge(int from, int to, int c, int f):
        from(from),
        to(to),
        c(c),
        f(f) {}
};

const int N = 100005;
const int INF = 1e9 + 7;
vector<Edge> e;
vector<int> g[N];
int used[N], t;


void upd(int ind, int f)
{
    e[ind].f += f;
    e[ind ^ 1].f -= f;
}

int dfs(int v, int can, int cur)
{
    if (v == t)
        return cur;
    used[v] = 1;
    for (int ind : g[v])
    {
        int u = e[ind].to, f = e[ind].f, c = e[ind].c;
        if (!used[u] &&  c - f >= can)
        {
            int len = dfs(u, can, min(cur, c - f));
            if (len)
            {
                upd(ind, len);
                return len;
            }
        }
    }
    return 0;
}

vector<int> val;
vector<vector<int> > ed;


int dfs2(int v, int cur)
{
    if (v == t)
        return cur;
    used[v] = 1;
    for (int ind : g[v])
    {
        int u = e[ind].to, f = e[ind].f;
        if (!used[u] && f > 0)
        {
            int len = dfs2(u, min(cur, f));
            if (len)
            {
                ed.back().push_back(ind);
                upd(ind, -len);
                return len;
            }
        }
    }
    return 0;
}

int solve()
{
    int n;
    if (!(cin >> n))
        return 1;
    int m, s;
    cin >> m;
    s = 0;
    t = n - 1;
    e.clear();
    for (int i = 0; i < n; i++)
        g[i].clear();
    val.clear();
    ed.clear();
    for (int i = 0; i < m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        x--;
        y--;
        g[x].push_back(sz(e));
        e.push_back(Edge(x, y, z, 0));
        g[y].push_back(sz(e));
        e.push_back(Edge(y, x, 0, 0));
    }
    for (int k = 30; k >= 0; k--)
        while (true)
        {
            for (int i = 0; i < n; i++)
                used[i] = 0;
            int x = dfs(s, (1 << k), INF);
            if (!x)
                break;
        }
    while (true)
    {
        for (int i = 0; i < n; i++)
            used[i] = 0;
        ed.push_back(vector<int>(0));
        val.push_back(dfs2(s, INF));
        if (!val.back())
            break;
    }
    val.pop_back();
    ed.pop_back();
    cout << sz(val) << endl;
    for (int i = 0; i < sz(val); i++)
    {
        cout << val[i] << ' ' << sz(ed[i]) << ' ';
        reverse(ed[i].begin(), ed[i].end());
        for (int j : ed[i])
            cout << j / 2 + 1 << ' ';
        cout << '\n';
    }
    return 1;
}

int32_t main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int TET = 1e9;
    //cin >> TET;
    while (TET--)
    {
        if (solve())
            break;
        #ifdef ONPC
            cout << "\n__________________________" << endl;
        #endif
    }
    #ifdef ONPC
        cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
    #endif
    return 0;
}