//Link solutie: https://www.infoarena.ro/job_detail/2961043?action=view-source
//a)Explicatie:Pentru a rezolva problema trebuie folosit algoritmul de flux maxim.
//Pentru asta, voi folosi algoritmul Edmonds-Karp. Intializam graful folosind matricea
//de adiacenta. Apoi, trasfer graful in graful rezidual, reprezentat tot de o matrice de
//adiacenta. Incep algoritmul prin construirea drumurilor de la sursa la nodul terminal
//de lungime minima, folosind bfs. Cat timp exista un astfel de drum, revizuiesc fluxul
//in lantul respectiv, si actualizez graful rezidual. Pentru ca algoritmul sa fie mai optim,
//la construirea lanturilor am exclus nodul terminal, drumul fiind reprezentat acum de
//drumul de la sursa la un nod legat de nodul terminal printr-o muchie nesaturata. Astfel,
//nu mai este nevoie sa refacem bfs-ul.
//Complexitate: O(n*m^2)
//b)Explicatie: Pentru a rezolva problema trebuie facuta taietura minima. Voi folosi un dfs
//pentru a determina ce noduri nu mai sunt accesibile din sursa dupa aplicarea fluxului maxim.
//Astfel, muchiile ce determina taietura minima sunt muchiile saturate, care contin nodurile ce
//nu mai sunt accesibile din sursa.
//Complexitate: O(n*m^2) (dfs O(n*m))
#include <bits/stdc++.h>
using namespace std;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
int n,m, graf[1001][1001],a,b,c,rgraf[1001][1001];
bool vizitat[1001];
vector<int> vecn;
//bfs pentru determinarea drumurilor de lungime minima de la sursa la nodurile legate
//direct de nodul terminal
bool bfs(int rgraf[1001][1001], int tata[], int n)
{
    for(int i=1;i<=n;i++)
        vizitat[i] = false;
    queue<int> q;
    q.push(1);
    vizitat[1] = true;
    tata[1] = -1;

    while(!q.empty())
    {
        int u = q.front();
        q.pop();

        for(int i = 1; i<=n;i++)
        {
            if(vizitat[i] == false && rgraf[u][i] > 0)
            {
                tata[i] = u;
                //daca s-a ajuns la nodul terminal, returnam true, dar nu mai actualizam
                //vectorul de tata
                if(i == n)
                {
                    return true;
                }

                q.push(i);
                vizitat[i] = true;
            }
        }
    }

    return false;

}
//b)
//dfs pentru determinarea taieturii minime
void dfs(int s, bool vizitat[])
{
    vizitat[s] = true;
    for(int i=1;i<=n+1;i++)
    {
        if(vizitat[i] == false && rgraf[1][i] != 0)
        {
            dfs(i,vizitat);
        }
    }
}
int main() {
    fin>>n>>m;
    //initializam graful
    for(int i=0;i<m;i++)
    {
        fin>>a>>b>>c;
        graf[a][b] = c;
    }
    //initializam graful rezidual
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            rgraf[i][j] = graf[i][j];
        }

    int tata[n+1], max_flow = 0;
    //determinam nodurile legate direct de nodul terminal
    for(int i=1;i<n;i++)
    {
        if(graf[i][n]>0)
            vecn.push_back(i);
    }
    //cat timp exista un drum de la sursa la un nod legat de nodul terminal
    while(bfs(rgraf, tata, n))
    {
        //optimizarea facuta pentru a nu reface bfs de mai multe ori
        for(int vec : vecn) {
            //daca vecinul nodului terminal face parte din drum si muchia vecin-destiantie
            //nu este saturata
            if(vizitat[vec] == true && rgraf[vec][n] > 0) {
                //actualizam vectorul de tati
                tata[n] = vec;
                //revizuiesc fluxul pe drum
                int capacitate_drum = INT_MAX;

                for (int i = n; i != 1; i = tata[i]) {
                    int u = tata[i];
                    capacitate_drum = min(capacitate_drum, rgraf[u][i]);
                }
                //actualizez graful rezidual
                for (int i = n; i != 1; i = tata[i]) {
                    int u = tata[i];
                    rgraf[u][i] -= capacitate_drum;
                    rgraf[i][u] += capacitate_drum;
                }
                //actualizez fluxul maxim
                max_flow += capacitate_drum;
            }
        }
    }
    //b)
    bool dfs_vizitat[1001];
    for(int i=0;i<=n+1;i++)
    {
        dfs_vizitat[i] = false;
    }
    dfs(1, dfs_vizitat);
    //stabilim muchiile ce determina taietura minima
    for(int i=0;i<n+1;i++)
    {
        for(int j=0;j<n+1;j++)
        {
            //daca muchia este saturata si nu s-a putut ajunge la unul dintre nodurile ce determina
            //muchia pornind din nodul sursa
            if(rgraf[i][j] == 0 && rgraf[j][i] != 0 && dfs_vizitat[i] == true && dfs_vizitat[j] == false)
                cout<<i<<" "<<j<<endl;
        }
    }
    fout<<max_flow;
    return 0;
}