#include <bits/stdc++.h>
#define N 1005
using namespace std;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
int n,m,capacity[N][N],maxflow,new_flow;
int S,D,T[N];
vector<int>g[N];
bitset<N>viz;
int bfs()
{
    fill(T,T+n+1,0);
    viz.reset();
    queue<pair<int,int> >q;
    q.push({S,2e9});
    viz[S]=1;
    while(!q.empty())
    {
        int nod=q.front().first;
        int new_flow=q.front().second;
        q.pop();
        for(auto i:g[nod])
            if(!viz[i] && capacity[nod][i])
            {
                viz[i]=1;T[i]=nod;//cout<<T[i]<<" ";
                cout<<nod<<" "<<i<<"\n";
                new_flow=min(new_flow,capacity[nod][i]);
                if(i==D) return new_flow;
                q.push({i,new_flow});
            }
    }
    return 0;
}
void Drum(int x)
{
    if(T[x]) Drum(T[x]);
    capacity[x][T[x]]+=new_flow,
    capacity[T[x]][x]-=new_flow;
}
int main()
{
    int x,y,cost;
    fin>>n>>m;
    S=1;D=n;
    while(m--)
    {
        fin>>x>>y>>cost;
        g[x].push_back(y);
        g[y].push_back(x);
        capacity[x][y]=capacity[y][x]=cost;
    }
    while(new_flow=bfs())
    {
        maxflow+=new_flow;
        Drum(D);
    }
    fout<<maxflow;
    return 0;
}