<|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.

252. Railway Communication
time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard



There are N towns in the country, connected with M railroads. All railroads are one-way, the railroad system is organized in such a way that there are no cycles. It's necessary to choose the best trains schedule, taking into account some facts.
Train path is the sequence of towns passed by the train. The following conditions must be satisfied.
1) At most one train path can pass along each railroad.
2) At most one train path can pass through each town, because no town can cope with a large amount of transport.
3) At least one train path must pass through each town, or town economics falls into stagnation.
4) The number of paths must be minimal possible.
Moreover, every railroad requires some money for support, i-th railroad requires c[i] coins per year to keep it intact. That is why the president of the country decided to choose such schedule that the sum of costs of maintaining the railroads used in it is minimal possible. Of course, you are to find such schedule.

Input
The first line of input contains two integers N and M (1<=N<=100; 0<=M<=1000). Next M lines describe railroads. Each line contains three integer numbers a[i], b[i] and c[i] - the towns that the railroad connects (1<=a[i]<=N; 1<=b[i]<=N, a[i]<>b[i]) and the cost of maintaining it (0<=c[i]<=1000). Since the road is one-way, the trains are only allowed to move along it from town a[i] to town b[i]. Any two towns are connected by at most one railroad.

Output
On the first line output K - the number of paths in the best schedule and C - the sum of costs of maintaining the railroads in the best schedule.
After that output K lines, for each train path first output L[i] (1<=L[i]<=N) - the number of towns this train path uses, and then L[i] integers identifying the towns on the train path. If there are several optimal solutions output any of them.

Sample test(s)

Input
4 4
1 2 1
1 3 2
3 4 2
2 4 2

Output
2 3
2 1 2
2 3 4
Author:	Sergey Simonchik
Resource:	Petrozavodsk Summer Training Sessions 2004
Date:	August 25, 2004

<|response|>
## 1) Abridged problem statement (concise)

You are given a **directed acyclic graph (DAG)** with **N towns** (vertices) and **M one-way railroads** (edges). You must choose a set of **directed paths** (“train paths”) such that:

- Each town belongs to **exactly one** chosen path (because “at most one” and “at least one” together).
- Paths follow directed railroads; each railroad can be used by **at most one** path.
- The **number of paths** is **minimum possible**.
- Among all solutions with the minimum number of paths, minimize the **sum of costs** of the used railroads.

Output the number of paths, the minimal total cost, and the paths themselves.

Constraints: \(1 \le N \le 100\), \(0 \le M \le 1000\), costs \(0..1000\).

---

## 2) Key observations

1. **Exactly-one constraint ⇒ vertex-disjoint path cover.**  
   Conditions (2) and (3) imply every town is visited by **exactly one** path, so we need a **vertex-disjoint path cover** of the DAG.

2. **Edges that “link” towns inside paths form a matching.**  
   In any set of vertex-disjoint paths, each vertex can have:
   - at most **one successor** (one chosen outgoing edge),
   - at most **one predecessor** (one chosen incoming edge).
   
   That’s precisely the definition of a **matching** if we split each vertex into a left copy (outgoing) and right copy (incoming).

3. **Minimizing number of paths ⇔ maximizing number of chosen linking edges.**  
   If we select \(k\) linking edges, they connect vertices into longer paths and reduce the number of paths by \(k\):
   \[
   \#paths = N - k
   \]
   So minimizing paths means **maximizing matching size**.

4. **Second objective (min cost) ⇒ min-cost maximum matching.**  
   Among all maximum matchings, pick one with minimum sum of edge costs. This is a classic **min-cost maximum matching in a bipartite graph**, solvable via **min-cost max-flow**.

5. **Reconstruction is easy.**  
   If the matching chooses edges \(u \to v\), set `nxt[u]=v` and mark `has_prev[v]=true`.  
   Path starts are exactly the vertices with `has_prev=false`.

---

## 3) Full solution approach

### Step A: Build a bipartite graph
Create two copies of towns:

- Left part: \(1..N\) (town as “can choose one outgoing link”)
- Right part: \(1..N\) (town as “can receive one incoming link”)

For every railroad \(a \to b\) with cost \(c\), add a bipartite edge \(a_L \to b_R\) with cost \(c\).

Choosing such an edge means: in the final schedule, town \(b\) comes immediately after town \(a\) in the same path.

### Step B: Reduce to min-cost max-flow
Create a flow network:

- Source \(S\)
- Left nodes \(L_i\) (town \(i\))
- Right nodes \(R_i\) (town \(i\))
- Sink \(T\)

Edges:
- \(S \to L_i\): capacity 1, cost 0 (at most one outgoing link from town \(i\))
- \(R_i \to T\): capacity 1, cost 0 (at most one incoming link to town \(i\))
- \(L_a \to R_b\): capacity 1, cost \(c(a,b)\) for each railroad

Run **min-cost max-flow** from \(S\) to \(T\):
- Maximum flow value = size of maximum matching = maximum number of links \(k\)
- Minimum cost among those max flows = minimum total railroad maintenance cost among schedules with minimum number of paths

Then:
- \(K = N - k\) is the minimum number of paths
- Total cost = min-cost of the max flow

### Step C: Reconstruct paths
From flow/matching edges \(L_a \to R_b\) that carry 1 unit:
- `nxt[a] = b`
- `has_prev[b] = true`

For each vertex \(v\) with `has_prev[v]==false`, start a path and follow `nxt` until it becomes 0.

Output those paths.

### Complexity
- Flow graph has \(\le 2N+2 \le 202\) nodes and \(\le M + 2N\) main edges.
- With successive shortest augmenting path + potentials + Dijkstra: easily fast for \(N \le 100, M \le 1000\).

---

## 4) C++ implementation (detailed comments)

```cpp
#include <bits/stdc++.h>
// #include <coding_library/graph/mincost_flow.hpp>

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<typename T>
class MinCostFlow {
  private:
    const static T inf = numeric_limits<T>::max();

    struct Edge {
        int to, rev;
        T capacity, cost, flow;
        Edge(int _to, int _rev, T _capacity, T _cost, T _flow)
            : to(_to),
              rev(_rev),
              capacity(_capacity),
              cost(_cost),
              flow(_flow) {}
    };

    int n;
    vector<vector<Edge>> g;
    vector<T> potential;
    vector<pair<int, int>> parent;
    vector<pair<T, T>> dist;

    void build_potential(int source) {
        fill(potential.begin(), potential.end(), inf);
        potential[source] = 0;

        while(true) {
            bool any = false;
            for(int v = 0; v < n; v++) {
                for(const auto& e: g[v]) {
                    if(e.capacity != 0 && potential[v] != inf &&
                       potential[v] + e.cost < potential[e.to]) {
                        potential[e.to] = potential[v] + e.cost;
                        any = true;
                    }
                }
            }
            if(!any) {
                break;
            }
        }
    }

    bool dijkstra(int source, int sink, T flow_limit, T flow) {
        fill(dist.begin(), dist.end(), make_pair(inf, flow_limit - flow));
        dist[source].first = 0;

        priority_queue<pair<T, int>, vector<pair<T, int>>, greater<>> q;
        q.push({0, source});

        while(!q.empty()) {
            auto [cur_dist, v] = q.top();
            q.pop();
            if(cur_dist > dist[v].first) {
                continue;
            }

            for(const auto& e: g[v]) {
                if(potential[e.to] != inf &&
                   cur_dist + e.cost - potential[e.to] + potential[v] <
                       dist[e.to].first &&
                   e.flow < e.capacity) {
                    parent[e.to] = {v, e.rev};
                    dist[e.to] = {
                        cur_dist + e.cost - potential[e.to] + potential[v],
                        min(dist[v].second, e.capacity - e.flow)
                    };
                    q.push({dist[e.to].first, e.to});
                }
            }
        }
        return dist[sink].first != inf;
    }

  public:
    MinCostFlow(int _n = 0) { init(_n); }

    void init(int _n) {
        n = _n;
        g.assign(n, {});
        potential.resize(n);
        parent.resize(n);
        dist.resize(n);
    }

    int size() const { return n; }

    T edge_flow(int from, int id) const { return g[from][id].flow; }

    int add_edge(int from, int to, T capacity, T cost) {
        int id = g[from].size();
        g[from].push_back(
            Edge(to, g[to].size() + (from == to), capacity, cost, 0)
        );
        g[to].push_back(Edge(from, id, 0, -cost, 0));
        return id;
    }

    pair<T, T> flow(int source, int sink, T flow_limit = inf) {
        for(int v = 0; v < n; v++) {
            for(auto& e: g[v]) {
                e.flow = 0;
            }
        }

        T cost = 0, flow = 0;
        build_potential(source);

        while(flow < flow_limit && dijkstra(source, sink, flow_limit, flow)) {
            T delta = dist[sink].second;
            flow += delta;

            for(int v = sink; v != source; v = parent[v].first) {
                auto& e = g[parent[v].first][g[v][parent[v].second].rev];
                cost += e.cost * delta;
                e.flow += delta;
                g[v][parent[v].second].flow -= delta;
            }

            for(int i = 0; i < n; i++) {
                if(dist[i].first != inf) {
                    potential[i] += dist[i].first;
                }
            }
        }
        return {cost, flow};
    }
};

int n, m;
vector<tuple<int, int, int>> edges;
MinCostFlow<int> mcf;

void read() {
    cin >> n >> m;
    edges.resize(m);
    for(auto& [a, b, c]: edges) {
        cin >> a >> b >> c;
    }
}

void solve() {
    // The problem statement is a bit confusing, but we are essentially looking
    // for the minimum cost of a schedule that goes through every vertex exactly
    // once. However, the roads can be a single vertex, so we also want to
    // prioritize having as few paths as possible. This is a somewhat standard
    // problem - we need to select at most one road going out of a city, and at
    // most one coming in. We can create a bipartite graph for this, with a copy
    // of each vertex in each side. The constraint of having as few paths as
    // possible implies that we want a maximal matching in this graph
    // (otherwise, we can reduce the number of roads). In particular, for each
    // path there is exactly 1 node with 0 out degree, meaning that the number
    // of paths is n-selected_edges, or we want to maximize selected edges
    // (which happens in the maximum matching). Out of these maximum matchings,
    // we want to have the lowest sum of weights, which we can do with mincost
    // maxflow.

    int source = 0, sink = 2 * n + 1;
    mcf.init(2 * n + 2);

    for(int i = 1; i <= n; i++) {
        mcf.add_edge(source, i, 1, 0);
        mcf.add_edge(n + i, sink, 1, 0);
    }

    vector<int> edge_ids(m);
    for(int i = 0; i < m; i++) {
        auto [a, b, c] = edges[i];
        edge_ids[i] = mcf.add_edge(a, n + b, 1, c);
    }

    auto [cost, matching] = mcf.flow(source, sink);
    int num_paths = n - matching;

    vector<int> nxt(n + 1, 0);
    vector<bool> has_prev(n + 1, false);
    for(int i = 0; i < m; i++) {
        if(mcf.edge_flow(get<0>(edges[i]), edge_ids[i]) > 0) {
            auto [a, b, c] = edges[i];
            nxt[a] = b;
            has_prev[b] = true;
        }
    }

    cout << num_paths << ' ' << cost << '\n';
    for(int i = 1; i <= n; i++) {
        if(has_prev[i]) {
            continue;
        }
        vector<int> path;
        for(int v = i; v != 0; v = nxt[v]) {
            path.push_back(v);
        }
        cout << path.size();
        for(int v: path) {
            cout << ' ' << v;
        }
        cout << '\n';
    }
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys
import heapq

class MinCostMaxFlow:
    """
    Min-Cost Max-Flow with potentials + Dijkstra (successive shortest augmenting path).
    Graph is directed; we store residual edges explicitly.
    """

    def __init__(self, n: int):
        self.n = n
        self.g = [[] for _ in range(n)]  # adjacency list

    def add_edge(self, u: int, v: int, cap: int, cost: int):
        """
        Adds edge u->v with capacity cap and cost.
        Also adds reverse edge v->u with capacity 0 and -cost.
        Each edge: [to, rev_index, cap, cost]
        """
        fwd = [v, len(self.g[v]), cap, cost]
        rev = [u, len(self.g[u]), 0, -cost]
        self.g[u].append(fwd)
        self.g[v].append(rev)
        return len(self.g[u]) - 1  # index of forward edge in g[u]

    def run(self, s: int, t: int):
        n = self.n
        INF = 10**18

        flow = 0
        cost = 0

        # Potentials: with non-negative costs we can start with zeros.
        pot = [0] * n

        while True:
            dist = [INF] * n
            pv = [-1] * n  # parent vertex
            pe = [-1] * n  # parent edge index
            dist[s] = 0

            pq = [(0, s)]
            while pq:
                d, v = heapq.heappop(pq)
                if d != dist[v]:
                    continue
                for ei, e in enumerate(self.g[v]):
                    to, rev, cap, ecost = e
                    if cap <= 0:
                        continue
                    # reduced cost
                    nd = d + ecost + pot[v] - pot[to]
                    if nd < dist[to]:
                        dist[to] = nd
                        pv[to] = v
                        pe[to] = ei
                        heapq.heappush(pq, (nd, to))

            if dist[t] == INF:
                break  # max flow achieved

            # update potentials for all reachable nodes
            for i in range(n):
                if dist[i] < INF:
                    pot[i] += dist[i]

            # find bottleneck (will be 1 here)
            add = INF
            v = t
            while v != s:
                u = pv[v]
                ei = pe[v]
                add = min(add, self.g[u][ei][2])
                v = u

            # augment
            v = t
            while v != s:
                u = pv[v]
                ei = pe[v]
                to, rev, cap, ecost = self.g[u][ei]
                self.g[u][ei][2] -= add
                self.g[v][rev][2] += add
                cost += add * ecost
                v = u

            flow += add

        return flow, cost


def solve():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    it = iter(data)
    N = int(next(it))
    M = int(next(it))

    rails = []
    for _ in range(M):
        a = int(next(it)); b = int(next(it)); c = int(next(it))
        rails.append((a, b, c))

    # Flow network:
    # S=0
    # Left: 1..N
    # Right: N+1..2N
    # T=2N+1
    S = 0
    T = 2 * N + 1
    mcmf = MinCostMaxFlow(2 * N + 2)

    # S -> Left(i)
    for i in range(1, N + 1):
        mcmf.add_edge(S, i, 1, 0)
    # Right(i) -> T
    for i in range(1, N + 1):
        mcmf.add_edge(N + i, T, 1, 0)

    # Store positions of railroad edges for reconstruction
    rail_pos = []
    for (a, b, c) in rails:
        u = a         # Left(a)
        v = N + b     # Right(b)
        idx = mcmf.add_edge(u, v, 1, c)
        rail_pos.append((u, idx))

    matching, min_cost = mcmf.run(S, T)
    K = N - matching

    # Reconstruct selected edges (cap becomes 0 if used)
    nxt = [0] * (N + 1)
    has_prev = [False] * (N + 1)

    for (a, b, c), (u, idx) in zip(rails, rail_pos):
        e = mcmf.g[u][idx]
        # e[2] is residual cap
        if e[2] == 0:
            nxt[a] = b
            has_prev[b] = True

    out = []
    out.append(f"{K} {min_cost}")

    for i in range(1, N + 1):
        if has_prev[i]:
            continue
        path = []
        v = i
        while v != 0:
            path.append(v)
            v = nxt[v]
        out.append(str(len(path)) + " " + " ".join(map(str, path)))

    sys.stdout.write("\n".join(out))


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

---

If you want, I can also provide a version that uses a dedicated **min-cost bipartite matching** algorithm directly (Hungarian-style variants), but min-cost max-flow is simplest and robust for these constraints.