Алгоритм Диница

const ll MAXN = 200001;

vector<ll> num[MAXN], g[MAXN], c[MAXN], f[MAXN], lvl, p, used, ans, rev[MAXN];

ll n;

bool bfs()
{
    lvl[1] = 0;
    queue<ll> q;
    q.push(1);
    while (q.size())
    {
        ll v = q.front();
        q.pop();
        for (ll i = 0; i < g[v].size(); i++)
        {
            ll u = g[v][i];
            if (lvl[u] == -1 && c[v][i] > f[v][i])
            {
                lvl[u] = lvl[v] + 1;
                q.push(u);
            }
        }
    }
    return lvl[n] != -1;
}

ll dfs(ll v, ll flow)
{
    if (v == n || flow == 0)
        return flow;
    for (ll i = 0; i < g[v].size(); i++)
    {
        ll u = g[v][i];
        if (lvl[u] == lvl[v] + 1)
        {
            ll cur = dfs(u, min(flow, c[v][i] - f[v][i]));
            f[v][i] += cur;
            f[u][rev[v][i]] -= cur;
            if (cur)
                return cur;
        }
    }
    return 0;
}

void dfs1(ll v)
{
    used[v] = 1;
    for (ll i = 0; i < g[v].size(); i++)
        if (!used[g[v][i]] && c[v][i] > f[v][i])
            dfs1(g[v][i]);
}

int main()
{
    ll m;
    cin >> n >> m;
    for (ll i = 1; i <= m; i++)
    {
        ll k, l, w;
        cin >> k >> l >> w;
        g[k].push_back(l);
        f[k].push_back(0);
        num[k].push_back(i);
        c[k].push_back(0);
        rev[k].push_back(g[l].size());

        g[l].push_back(k);
        f[l].push_back(0);
        num[l].push_back(i);
        c[l].push_back(0);
        rev[l].push_back(g[k].size() - 1);
    }
    p.assign(n + 1, 0);
    while (true)
    {
        lvl.assign(n + 1, -1);
        if (!bfs())
            break;
        dfs(1, 1e9);
    }
    used.assign(n + 1, 0);
    dfs1(1);
    ll vel = 0;
    for (ll v = 1; v <= n; v++)
        if (used[v])
            for (ll j = 0; j < g[v].size(); j++)
                if (!used[g[v][j]])
                    ans.push_back(num[v][j]), vel += c[v][j];
    sort(ans.begin(), ans.end());
    cout << ans.size() << " " << vel << endl;
    for (ll i : ans)
        cout << i << " ";
    return 0;
}