#include<stdio.h>

 #include<string.h>

 #include<stdlib.h>

 #include<iostream>

 #include<algorithm>

 #include<queue>

 #include<stack>

 using namespace std;

 int mapx[][],ve[],vl[],h[],m,k;

 stack<int>zhan;

 queue<int>e;

 queue<int>l;

 void tuopu();

 void gengxin();

 int main()

 {

     while(cin>>m>>k)

     {

         memset(mapx,,sizeof(mapx));

         memset(h,,sizeof(h));

         memset(ve,,sizeof(ve));

         memset(vl,,sizeof(vl));

         int i,u,v,countx;

         for(i=; i<=k; i++)

         {

             cin>>u>>v>>countx;

             mapx[u][v]=countx;

             h[v]++;

         }

         tuopu();

         gengxin();

     }

 }

 void tuopu()

 {

     int i,flag=,j;

     while(flag=!flag)

     {

         for(i=; i<=m; i++)

         {

             if(h[i]==)

             {

                 flag=;

                 h[i]=-;

                 zhan.push(i);

                 for(j=; j<=m; j++)

                     if(mapx[i][j]!=)

                         h[j]--;

                 //更新 ve数组

                 int y=;

                 for(j=; j<=m; j++)

                 {

                     if(mapx[j][i]!=)

                     {

                         if(mapx[j][i]+ve[j]>y)

                         {

                             y=mapx[j][i]+ve[j];

                         }

                     }

                 }

                 ve[i]=y;

             }

         }

     }

     /*while(!zhan.empty())

     {

         cout<<zhan.top()<<" ";

         zhan.pop();

     }

     cout<<endl;*/

     //输出ve 数组

     /*for(i=1;i<=m;i++)

         cout<<ve[i]<<" ";

     cout<<endl;*/

 }

 void gengxin()

 {

     //更新 vl数组和v数组，e数组

     int i,j;

     int x=ve[m];

     for(i=; i<=m; i++)

         vl[i]=x;

     int maxx=x,z[],top=-,z1[];

     while(!zhan.empty())

     {

         x=zhan.top();

         int y=maxx;

         for(i=; i<=m; i++)

         {

             if(mapx[x][i]!=)

             {

                 if(y>vl[i]-mapx[x][i])

                     y=vl[i]-mapx[x][i];

             }

         }

         vl[x]=y;

         zhan.pop();

     }

     //验证输出vl数组

     /*for(i=1;i<=m;i++)

         cout<<vl[i]<<" ";

     cout<<endl;*/

     int countx=,q1=;

     for(i=; i<=m; i++)

     {

         for(j=; j<=m; j++)

         {

             if(mapx[i][j]!=)

             {

                 //e.push(ve[i]);

                 //l.push(vl[j]-mapx[i][j]);

                 if(ve[i]==vl[j]-mapx[i][j])

                 {

                     if(j==m)

                         q1=;

                     countx=countx+mapx[i][j];

                     z[++top]=i;

                     z1[top]=j;

                     break;

                 }

             }

         }

         if(q1==)break;

     }

     cout<<countx<<endl;

     for(i=; i<=top; i++)

         cout<<z[i]<<" "<<z1[i]<<endl;

     //验证输出

     /*

     while(!e.empty())

     {

         cout<<e.front()<<" ";

         e.pop();

     }

     cout<<endl;

     while(!l.empty())

     {

         cout<<l.front()<<" ";

         l.pop();

     }

     cout<<endl;*/

 }

 /*测试数据

 9 11

 1 2 6

 1 3 4

 1 4 5

 2 5 1

 3 5 1

 4 6 2

 5 7 8

 5 8 7

 6 8 4

 7 9 2

 8 9 4

 */