<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

402. Terrorists in Berland
Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



Many countries dream of capturing great and glorious country of Berland. Berland is a big country consisting of N cities, some of them are connected by bidirectional roads. Each pair of cities is connected by no more then one road. A traveler can get from one city to any other city traveling by the roads only.

Invaders plan to use these roads during their operation, but Berland military forces are strong enough to destroy an enemy trying to move along the roads. The treacherous plan was developed to make the invasion easier: Berland should be divided into two parts. To make the plan more effective the decision was made to use terrorists from the Berland opposition. Several groups agreed to participate in the plan. The terrorists' resources are limited, so they can only destroy roads, not cities. The procedure of the road destruction is a costly operation. The security precautions on different roads can vary, so the cost of the road destruction can be different.

Invaders want to suddenly attack Berland without declaring the war and quickly capture one of the cities. Berland troops can't move through the captured city as they can't move along the destroyed roads.

Your task is to find cheapest plan of roads destruction, so that at least one city exists which can be captured and allow invaders to divide the country into two parts. Berland is considered divided, if two such cities exist, that there is no way along non-destroyed roads and through non-captured cities from one to another.

Input
The first line of the input contains two integer numbers N and M (3 ≤ N ≤ 50; 1 ≤ M ≤ 500), where N is the number of cities and M is the number of roads. The following M lines contain the description of the roads given as three integer numbers ai, bi, wi (1 ≤ ai < bi ≤ N; 1 ≤ wi ≤ 10). The cost of destruction of the the road from ai to bi is wi.

Output
Write to the first line the total amount of money required to destroy roads in the optimal plan. Write to the second line K — number of roads to be destroyed according to the plan. Write to the third line numbers of roads to be destroyed divided by one space. The roads are numbered in order of appearance in the input. If there are several solutions, choose any of them.

Example(s)
sample input
sample output
3 3
1 2 1
2 3 2
1 3 2
1
1
1

sample input
sample output
4 6
1 2 1
1 3 1
2 3 2
1 4 1
2 4 2
3 4 3
2
2
2 4

<|response|>
1. Abridged problem statement
We have an undirected, connected graph with N cities (nodes) and M roads (edges). Each road has a destruction cost. We want to choose one city to "capture" (remove it) and destroy some roads so that the remaining graph becomes disconnected. Find the minimum total destruction cost and report which roads to destroy.

2. Key observations
- Capturing city t removes t and all its incident edges. To disconnect the remaining graph, we must cut all paths between at least two surviving nodes s and sink.
- In the graph G−t, finding the cheapest set of edges whose removal separates s from sink is exactly the minimum s–t cut between s and sink.
- We only need to consider pairs (s, sink) that are both neighbours of t in the original graph. If the graph splits, its components on either side of the cut must contain different neighbours of t.
- A virtual city 0 adjacent to all real cities is added to handle the case where no real city needs to be captured.
- Therefore, for each candidate t from 0 to N, and for each ordered pair s < sink among neighbours of t, we compute the min-cut in G−t between s and sink and keep the globally cheapest.

3. Full solution approach
- Read N, M, and the list of edges (with weights and original indices). Build an adjacency list.
- Add a virtual city 0 adjacent to all cities 1..N.
- For every city t = 0..N:
  • Let nbrs = list of neighbours of t.
  • For each pair s < sink in nbrs:
    – Build a flow network on nodes 1..N but skip any edge incident to t.
    – For every remaining undirected edge (a,b) with weight w and index idx, add two directed edges a→b and b→a with capacity w and store idx for later identification.
    – Compute max-flow from s to sink (this equals min-cut capacity).
    – If this flow is less than the best so far, reconstruct the cut:
       · From s, do a DFS in the residual graph following edges with residual capacity > 0 to mark reachable nodes.
       · Any original edge (by idx) going from a reachable node to a non-reachable node is in the cut. Collect these indices.
       · Update the global best cost and best list of indices.
- Print the best cost, the number of edges in the cut, and the sorted list of their original indices.

4. C++ implementation with detailed comments
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

template<class FlowT>
class MaxFlow {
  public:
    const static FlowT finf = 1e9 + 42 + 17;

    struct Edge {
        FlowT flow, cap;
        int idx, rev, to;
        Edge() : flow(0), cap(0), idx(0), rev(0), to(0) {}
        Edge(int _to, int _rev, FlowT _flow, FlowT _cap, int _idx)
            : flow(_flow), cap(_cap), idx(_idx), rev(_rev), to(_to) {}
    };

    int n;
    vector<vector<Edge>> g;
    vector<int> dist, po;
    vector<char> used_cut;

    void init(int _n) {
        n = _n;
        g.assign(n + 1, {});
        dist.assign(n + 1, -1);
        po.assign(n + 1, 0);
        used_cut.assign(n + 1, 0);
    }

    void add_edge(int u, int v, FlowT w, int idx = -1) {
        g[u].push_back(Edge(v, g[v].size(), 0, w, idx));
        g[v].push_back(Edge(u, g[u].size() - 1, 0, 0, -1));
    }

    bool bfs(int s, int t) {
        for(int v = 0; v <= n; v++) {
            dist[v] = -1;
            po[v] = 0;
        }

        queue<int> q;
        q.push(s);
        dist[s] = 0;
        while(!q.empty()) {
            int u = q.front();
            q.pop();
            for(Edge e: g[u]) {
                if(dist[e.to] == -1 && e.flow < e.cap) {
                    dist[e.to] = dist[u] + 1;
                    q.push(e.to);
                }
            }
        }

        return dist[t] != -1;
    }

    FlowT dfs(int u, int t, FlowT fl = finf) {
        if(u == t) {
            return fl;
        }

        for(; po[u] < (int)g[u].size(); po[u]++) {
            auto& e = g[u][po[u]];
            if(dist[e.to] == dist[u] + 1 && e.flow < e.cap) {
                FlowT f = dfs(e.to, t, min(fl, e.cap - e.flow));
                e.flow += f;
                g[e.to][e.rev].flow -= f;
                if(f > 0) {
                    return f;
                }
            }
        }

        return 0;
    }

    FlowT flow(int s, int t) {
        if(s == t) {
            return finf;
        }

        FlowT ret = 0, to_add;
        while(bfs(s, t)) {
            while((to_add = dfs(s, t))) {
                ret += to_add;
            }
        }

        return ret;
    }

    void dfs_min_cut(int u) {
        used_cut[u] = 1;
        for(auto e: g[u]) {
            if(!used_cut[e.to] && e.cap > e.flow) {
                dfs_min_cut(e.to);
            }
        }
    }

    void find_cut(int s) {
        for(int i = 0; i <= n; i++) {
            used_cut[i] = 0;
        }
        dfs_min_cut(s);
    }
};

int n, m;
vector<pair<int, pair<int, int>>> ed;
vector<vector<int>> adj;

void read() {
    cin >> n >> m;
    ed.assign(m + 1, {});
    adj.assign(n + 1, {});
    for(int i = 1; i <= m; i++) {
        cin >> ed[i].first >> ed[i].second.first >> ed[i].second.second;
        adj[ed[i].first].push_back(ed[i].second.first);
        adj[ed[i].second.first].push_back(ed[i].first);
    }
}

int answer;
vector<int> ans;
MaxFlow<int> mf;

void check(int t, int s, int sink) {
    mf.init(n);
    for(int i = 1; i <= m; i++) {
        if(ed[i].first != t && ed[i].second.first != t) {
            mf.add_edge(
                ed[i].first, ed[i].second.first, ed[i].second.second, i
            );
            mf.add_edge(
                ed[i].second.first, ed[i].first, ed[i].second.second, i
            );
        }
    }

    int curr = mf.flow(s, sink);
    if(answer == -1 || curr < answer) {
        mf.find_cut(s);
        answer = curr;
        ans.clear();
        for(int i = 0; i <= n; i++) {
            for(auto it: mf.g[i]) {
                if(mf.used_cut[i] && !mf.used_cut[it.to] && it.idx != -1) {
                    ans.push_back(it.idx);
                }
            }
        }

        sort(ans.begin(), ans.end());
        ans.erase(unique(ans.begin(), ans.end()), ans.end());
    }
}

void solve_captured(int r) {
    for(int u: adj[r]) {
        for(int v: adj[r]) {
            if(u < v && r != u && r != v) {
                check(r, u, v);
            }
        }
    }
}

void solve() {
    // The invaders capture one city t (Berland troops cannot route through it)
    // and then need at least two surviving cities disconnected from each other.
    // Cutting roads to separate a fixed pair s, sink is exactly a min cut in
    // the graph with t removed, where each undirected road becomes a pair of
    // directed edges with capacity equal to its destruction cost.
    //
    // We brute force the captured city t (including a virtual city 0 adjacent
    // to all cities, which covers the case where no city is captured) and the
    // ordered pair s < sink among neighbours of t. Both s and sink must lie on
    // either side of the eventual cut, and any separating cut must split some
    // such neighbour pair, so this enumeration is sufficient. For each choice
    // we run Dinic, take the cheapest cut overall, and recover the cut edges by
    // a reachability DFS from s over residual capacity: edges leaving the
    // reachable set with a valid input index form the plan.

    adj.resize(n + 1);
    for(int i = 1; i <= n; i++) {
        adj[0].push_back(i);
    }

    answer = -1;
    for(int i = 0; i <= n; i++) {
        solve_captured(i);
    }

    cout << answer << '\n';
    cout << ans.size() << '\n';
    cout << ans;
    if(!ans.empty()) {
        cout << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    read();
    solve();

    return 0;
}
```

5. Python implementation with detailed comments
```python
import sys
from collections import deque
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

class Dinic:
    def __init__(self, n):
        self.n = n
        self.adj = [[] for _ in range(n+1)]
    def add_edge(self, u, v, cap, idx=-1):
        # forward edge: [to, cap, idx, rev_index]
        self.adj[u].append([v, cap, idx, len(self.adj[v])])
        # backward edge with zero cap
        self.adj[v].append([u, 0, -1, len(self.adj[u]) - 1])
    def bfs(self, s, t, level):
        for i in range(len(level)):
            level[i] = -1
        q = deque([s])
        level[s] = 0
        while q:
            u = q.popleft()
            for v, cap, _, _ in self.adj[u]:
                if cap > 0 and level[v] < 0:
                    level[v] = level[u] + 1
                    q.append(v)
        return level[t] >= 0
    def dfs(self, u, t, f, level, it):
        if u == t or f == 0:
            return f
        for i in range(it[u], len(self.adj[u])):
            it[u] = i
            v, cap, _, rev = self.adj[u][i]
            if cap > 0 and level[v] == level[u] + 1:
                pushed = self.dfs(v, t, min(f, cap), level, it)
                if pushed:
                    # update residual graph
                    self.adj[u][i][1] -= pushed
                    self.adj[v][rev][1] += pushed
                    return pushed
        return 0
    def maxflow(self, s, t):
        flow = 0
        level = [-1] * (self.n + 1)
        while self.bfs(s, t, level):
            it = [0] * (self.n + 1)
            while True:
                pushed = self.dfs(s, t, 10**18, level, it)
                if not pushed:
                    break
                flow += pushed
        return flow
    def min_cut_reachable(self, s):
        # after maxflow, see which nodes reachable from s in residual graph
        vis = [False] * (self.n + 1)
        stack = [s]
        vis[s] = True
        while stack:
            u = stack.pop()
            for v, cap, _, _ in self.adj[u]:
                if cap > 0 and not vis[v]:
                    vis[v] = True
                    stack.append(v)
        return vis

def main():
    N, M = map(int, input().split())
    edges = [None] * (M+1)
    adj = [[] for _ in range(N+1)]
    for i in range(1, M+1):
        a,b,w = map(int, input().split())
        edges[i] = (a,b,w)
        adj[a].append(b)
        adj[b].append(a)

    best_cost = None
    best_cut = []

    # try capturing each city r
    for r in range(1, N+1):
        nbrs = adj[r]
        L = len(nbrs)
        # each unordered pair of neighbors
        for i in range(L):
            for j in range(i+1, L):
                u, v = nbrs[i], nbrs[j]
                # build flow network on 1..N excluding edges at r
                din = Dinic(N)
                for idx in range(1, M+1):
                    a,b,w = edges[idx]
                    if a==r or b==r: continue
                    din.add_edge(a, b, w, idx)
                    din.add_edge(b, a, w, idx)
                cost = din.maxflow(u, v)
                if best_cost is None or cost < best_cost:
                    reach = din.min_cut_reachable(u)
                    cut_ids = set()
                    for x in range(1, N+1):
                        if not reach[x]:
                            continue
                        for to, cap, idx, _ in din.adj[x]:
                            if not reach[to] and idx != -1:
                                cut_ids.add(idx)
                    best_cost = cost
                    best_cut = sorted(cut_ids)

    # output the result
    print(best_cost)
    print(len(best_cut))
    if best_cut:
        print(*best_cut)

if __name__ == "__main__":
    main()
```
