#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream in("maxflow.in");
ofstream out("maxflow.out");

const int inf = 1000000000;

int n, m, x, y, z;
vector<vector<int>> capacity, flow;
vector<bool> viz;
vector<int> height, excess, seen;
queue<int> excess_vertices;
vector<int> vertices_set;

void DFS(int nod){
    viz[nod] = 1;
    vertices_set.push_back(nod);
    for(int i = 0; i < n; i++){
        if(!viz[i] && capacity[nod][i] < 0){
            DFS(i);
        }
    }
}

void push(int u, int v)
{
    int d = min(excess[u], capacity[u][v] - flow[u][v]);
    flow[u][v] += d;
    flow[v][u] -= d;
    excess[u] -= d;
    excess[v] += d;
    if (d && excess[v] == d)
        excess_vertices.push(v);
}

void relabel(int u)
{
    int d = inf;
    for (int i = 0; i < n; i++) {
        if (capacity[u][i] - flow[u][i] > 0)
            d = min(d, height[i]);
    }
    if (d < inf)
        height[u] = d + 1;
}

void discharge(int u)
{
    while (excess[u] > 0) {
        if (seen[u] < n) {
            int v = seen[u];
            if (capacity[u][v] - flow[u][v] > 0 && height[u] > height[v])
                push(u, v);
            else
                seen[u]++;
        } else {
            relabel(u);
            seen[u] = 0;
        }
    }
}

int max_flow(int s, int t)
{
    height.assign(n, 0);
    height[s] = n;
    flow.assign(n, vector<int>(n, 0));
    excess.assign(n, 0);
    excess[s] = inf;
    for (int i = 0; i < n; i++) {
        if (i != s)
            push(s, i);
    }
    seen.assign(n, 0);

    while (!excess_vertices.empty()) {
        int u = excess_vertices.front();
        excess_vertices.pop();
        if (u != s && u != t)
            discharge(u);
    }

    int max_flow = 0;
    for (int i = 0; i < n; i++)
        max_flow += flow[i][t];
    return max_flow;
}

int main() {
    in >> n >> m;
    capacity.assign(n, vector<int>(n, 0));
    for(int i = 1; i <= m; i++){
        in >> x >> y >> z;
        capacity[x - 1][y - 1] = z;
    }
    out << max_flow(0, n - 1) << '\n';
    //min-cut intre nodurile 0 si n - 1
    viz.assign(n, 0);
    x = 0;
    y = n - 1;
    out << "Min-cut: " << max_flow(x, y) << '\n';
    out << "Edges set: ";
    DFS(x);
    for(auto& nod : vertices_set){
        for(int i = 0; i < n; i++){
            if(capacity[nod][i] > 0)
                out << nod << " - " << i << '\n';
        }
    }
    return 0;
}