#include <fstream>
#include <queue>
#include <cstring>
#include <iostream>

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

const int NMAX=1001;

int cap[NMAX][NMAX];
int flux[NMAX][NMAX];
int nr1[NMAX];
int nr2[NMAX];
int tata[NMAX];
bool viz[NMAX];
int s,d;
int n,m;
std::queue<int>q;
bool bfs(){
    while(!q.empty())
        q.pop();
    q.push(s);
    memset(viz,0,sizeof(viz));
    viz[s]=1;
    tata[s]=1;
    while(!q.empty()){
        int vf=q.front();
        q.pop();
        for(int i=1;i<=n;i++)
            if(!viz[i] && flux[vf][i]<cap[vf][i]){
                tata[i]=vf;
                if(i==d)
                    return 1;
                q.push(i);
                viz[i]=1;
            }
    }
    return 0;
}

int drum(int nn){
    int t=tata[nn],nod=nn,mini=1<<30;
    while(nod!=1){
        mini=std::min(mini,cap[t][nod]-flux[t][nod]);
        nod=t;
        t=tata[t];
    }
    return mini;
}

void act(int flow){
    int t=tata[n],nod=n;
    while(nod!=1){
        flux[t][nod]+=flow;
        flux[nod][t]-=flow;
        nod=t;
        t=tata[t];
    }
}

int main(){
    in>>n>>m;
    for(int i=1,x,y,c;i<=m;i++)
        in>>x>>y>>c,cap[x][y]=c,nr1[x]++,nr2[y]++;
    for(int i=1;i<=n;i++){
        if(nr1[i]==0)
            d=i;
        if(nr2[i]==0)
            s=i;
    }
    std::cout<<s<<" "<<d<<'\n';
    int rez=0;
    while(bfs()){
        int f=drum(d);
        act(f);
        rez+=f;
    }
    out<<rez;
    return 0;
}