<|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>
using namespace std;

/*
  Min-Cost Max-Flow (Successive Shortest Augmenting Path)
  using Johnson potentials + Dijkstra for non-negative reduced costs.

  Works well here because:
  - graph is small (<= 202 nodes),
  - capacities are integers (0/1),
  - costs are non-negative (0..1000).
*/

template <class T>
struct MinCostMaxFlow {
    struct Edge {
        int to, rev;     // destination and index of reverse edge in g[to]
        T cap;           // remaining capacity
        T cost;          // cost per unit of flow
    };

    int n;
    vector<vector<Edge>> g;
    vector<T> pot;       // potentials
    vector<T> dist;      // dijkstra distances (reduced costs)
    vector<int> pv, pe;  // parent vertex/edge to reconstruct shortest path

    static constexpr T INF = numeric_limits<T>::max() / 4;

    MinCostMaxFlow(int n = 0) { init(n); }

    void init(int n_) {
        n = n_;
        g.assign(n, {});
        pot.assign(n, 0);
        dist.assign(n, 0);
        pv.assign(n, -1);
        pe.assign(n, -1);
    }

    // Add directed edge u->v with capacity cap and cost cost.
    void add_edge(int u, int v, T cap, T cost) {
        Edge a{v, (int)g[v].size(), cap, cost};
        Edge b{u, (int)g[u].size(), 0, -cost};
        g[u].push_back(a);
        g[v].push_back(b);
    }

    // Min-cost max-flow from s to t.
    // Returns {flow, cost}.
    pair<T,T> run(int s, int t) {
        T flow = 0, cost = 0;

        // Since costs are non-negative, starting potentials = 0 is fine.
        // (If negative costs existed, we'd run Bellman-Ford once.)

        while (true) {
            // Dijkstra on reduced costs: rcost(u->v)=cost + pot[u]-pot[v]
            fill(dist.begin(), dist.end(), INF);
            fill(pv.begin(), pv.end(), -1);
            fill(pe.begin(), pe.end(), -1);

            dist[s] = 0;
            priority_queue<pair<T,int>, vector<pair<T,int>>, greater<pair<T,int>>> pq;
            pq.push({0, s});

            while (!pq.empty()) {
                auto [d, v] = pq.top();
                pq.pop();
                if (d != dist[v]) continue;

                for (int i = 0; i < (int)g[v].size(); i++) {
                    const Edge &e = g[v][i];
                    if (e.cap <= 0) continue;

                    T nd = d + e.cost + pot[v] - pot[e.to];
                    if (nd < dist[e.to]) {
                        dist[e.to] = nd;
                        pv[e.to] = v;
                        pe[e.to] = i;
                        pq.push({nd, e.to});
                    }
                }
            }

            if (dist[t] == INF) break; // no augmenting path => max flow reached

            // Update potentials: pot[v] += dist[v] for all reachable v
            for (int i = 0; i < n; i++) {
                if (dist[i] < INF) pot[i] += dist[i];
            }

            // Find bottleneck capacity along path s->t (here it will be 1)
            T add = INF;
            for (int v = t; v != s; v = pv[v]) {
                int u = pv[v];
                int ei = pe[v];
                add = min(add, g[u][ei].cap);
            }

            // Augment
            for (int v = t; v != s; v = pv[v]) {
                int u = pv[v];
                int ei = pe[v];
                Edge &e = g[u][ei];
                Edge &re = g[v][e.rev];
                e.cap -= add;
                re.cap += add;
                cost += add * e.cost;
            }

            flow += add;
        }

        return {flow, cost};
    }
};

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

    int N, M;
    cin >> N >> M;

    struct Rail { int a, b, c; };
    vector<Rail> rails(M);
    for (int i = 0; i < M; i++) {
        cin >> rails[i].a >> rails[i].b >> rails[i].c;
    }

    // Node indexing in flow network:
    // S = 0
    // Left towns: 1..N
    // Right towns: N+1..2N
    // T = 2N+1
    int S = 0, T = 2 * N + 1;
    MinCostMaxFlow<int> mcmf(2 * N + 2);

    // S -> Left(i), capacity 1
    for (int i = 1; i <= N; i++) {
        mcmf.add_edge(S, i, 1, 0);
    }
    // Right(i) -> T, capacity 1
    for (int i = 1; i <= N; i++) {
        mcmf.add_edge(N + i, T, 1, 0);
    }

    // Remember where each railroad edge is stored so we can later check if used.
    // We'll store (from_node, edge_index_in_g[from_node]).
    vector<pair<int,int>> railEdgePos(M);

    for (int i = 0; i < M; i++) {
        int a = rails[i].a;
        int b = rails[i].b;
        int c = rails[i].c;

        int from = a;       // Left(a)
        int to = N + b;     // Right(b)

        // store position of forward edge
        railEdgePos[i] = {from, (int)mcmf.g[from].size()};
        mcmf.add_edge(from, to, 1, c);
    }

    // Run min-cost max-flow => min-cost maximum matching
    auto [matchingSize, minCost] = mcmf.run(S, T);

    int K = N - (int)matchingSize; // minimum number of paths

    // Reconstruct matching:
    // If a railroad edge was used, its residual capacity becomes 0 (it was 1).
    vector<int> nxt(N + 1, 0);
    vector<char> has_prev(N + 1, 0);

    for (int i = 0; i < M; i++) {
        auto [from, idx] = railEdgePos[i];
        const auto &e = mcmf.g[from][idx];
        // If cap==0, we sent 1 unit through it => chosen in matching
        if (e.cap == 0) {
            int a = rails[i].a;
            int b = rails[i].b;
            nxt[a] = b;
            has_prev[b] = 1;
        }
    }

    cout << K << ' ' << minCost << "\n";

    // Output each path starting from nodes with no predecessor.
    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";
    }

    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.