#include <iostream>
#include <fstream>
#include <queue>
#define nmax 10001
using namespace std;
int a[nmax][nmax], c[nmax][nmax], f[nmax][nmax];
int viz[nmax], T[nmax];
int n, m, lung, minim;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
struct arc { int n1, n2; };
arc drum[101];
int bf()
{
    int i, j;
    queue <int> q;
    fill(viz, viz + nmax, 0); fill(T, T + nmax, 0);
    q.push(1);
        viz[1] = 1;
    while (q.empty() != 1)
    {
        i = q.front();
        if (i == n)
            return 1;
        q.pop();
        for (j = 1; j <= n; j++)
        {
            if (viz[j] == 0 && c[i][j] - f[i][j] > 0)
            {//arc parcurs in sens direct
                viz[j] = 1;
                T[j] = i;
                q.push(j);
            }
            if (viz[j] == 0 && f[j][i] > 0)
            {//arc parcurs in sens invers
                viz[j] = 1;
                T[j] = i;
                q.push(j);
            }
        }
    }
    return 0;
}
void calcdrum()
{
    int i = 0, b = n, a;
    minim = 10000000;
    a = T[b];
    while (a != 0)
    {
        drum[i].n1 = a;
        drum[i].n2 = b;
        if (c[a][b] > f[a][b])
        {
            if (minim > c[a][b] - f[a][b])
                minim = c[a][b] - f[a][b];
        }
        else
            if (minim > f[b][a])
                minim = f[b][a];
        i++;
        b = a;
        a = T[b];
    }
    lung = i;
}
 
 
int main()
{
    int i, j, k, ok = 1;
    fin >> n >> m;
    for (i = 0; i < m; i++)
    {
        fin >> i >> j;
        fin >> c[i][j];
    }
    while (ok == 1)
    {
        ok = bf(); //returneaza 1 daca gaseste un drum
        if (ok == 1)
        {
            calcdrum(); //calculeaza si minimul
            cout << "\n\ngasit un drum de lungime " << lung;
            cout << " capacitate reziduala " << minim << endl;
            cout << "format din arcele: ";
            for (k = 0; k < lung; k++)
            {
                i = drum[k].n1;
                j = drum[k].n2;
               cout << i << '-' << j << " , ";
                if (c[i][j] - f[i][j] > 0)
                    f[i][j] += minim;
                else
                    f[j][i] -= minim;
            }
        }
    }
    int fluxmax = 0;
    for (i = 1; i <= n; i++)
        fluxmax += f[1][i];
    cout << "\n\nflux maxim= " << fluxmax << endl;
    cout << "starea fiecarui arc:capacitate/flux\n";
    int suma = 0;
    int maxflow = 0;
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= n; j++)
            if (c[i][j] > 0)
            {
                suma += f[i][j];
                cout << '(' << i << '-' << j << "):";
                cout << c[i][j] << '/' << f[i][j] << endl;
            }
        if (maxflow < suma)
            maxflow = suma;
        suma = 0;
    }
    fout << maxflow;
    return 0;
}