#include <fstream>
#include <queue>
using namespace std;
ifstream in("maxflow.in");
ofstream out("maxflow.out");
int n,m,c[1001][1001],f[1001][1001];
int bf(int n1,int n2,int t[]){
    queue <int> q;
    int v[1001];
    for(int i=1;i<=n+1;i++){
        v[i]=0;
    }
    q.push(n1);
    v[n1]=1;
    while(!q.empty() && v[n2]==0){
        int nod=q.front();
        q.pop();
        for(int i=1;i<=n;i++){
            if(c[nod][i]-f[nod][i]>0 && v[i]==0){
                q.push(i);
                v[i]=1;
                t[i]=nod;
            }
            if(f[i][nod]>0 && v[i]==0){
                q.push(i);
                v[i]=1;
                t[i]=nod;
            }
        }
    }
    return v[n2];
}
int main()
{
    //citire date
    in>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,cp;
        in>>x>>y>>cp;
        c[x][y]=cp;
    }
    int t[n+1],ni=1,nf=n;
    t[1]=0;
    while(bf(ni,nf,t)==1){ // cat timp mai gaseste un drum rezidual
        // calculeaza cantitatea ce poate fi transportata prin drum
        int i=nf,cant=110001;
        while(i!=ni){
            if(c[t[i]][i]-f[t[i]][i]>0){
                if(cant>c[t[i]][i]-f[t[i]][i])
                    cant=c[t[i]][i]-f[t[i]][i];
            }
            else{
                if(cant>f[i][t[i]])
                    cant=f[i][t[i]];
            }
            i=t[i];
        }
        // actualizeaza fluxul
        i=nf;
        while(i!=ni){
            out<<i<<" ";
            if(c[t[i]][i]-f[t[i]][i]>0){
                f[t[i]][i]=f[t[i]][i]+cant;
            }
            else{
                f[i][t[i]]=f[i][t[i]]-cant;
            }
            i=t[i];
        }
        out<<i<<endl;
    }
    int s=0;
    for(int i=1;i<=n;i++){
        s=s+f[1][i];
    }
    out<<s<<endl;
    return 0;
}