#include<iostream>
using namespace std;
long q[220][220],qs[220][220],n,m,s=0,k[1000000];

long go(long a,long b)
{
     long i,j,r=0;
     if(a==m)
     {
        return b;
     }
     for(i=1;i<=m;i++)
     {
        if(q[a][i]>0&&k[i]==0&&q[a][i]>qs[a][i])
        {
           if(q[a][i]-qs[a][i]<b)j=q[a][i]-qs[a][i];
           else j=b;
           r=go(i,j);
           qs[a][i]=qs[a][i]+r;
           if(r==0)continue;
           else break;
        }
        if(q[i][a]>0&&k[i]==0&&qs[i][a]>0)
        {
           if(qs[a][i]<b)j=qs[a][i];
           else j=b;
           r=go(i,j);
           qs[a][i]=qs[a][i]+r;
           if(r==0)continue;
           else break;
        }
     }
     if(i==m&&q[a][m]<=0)
     {
        return 0;
     }
     else
     {
        return r;
     }
} 

int main()
{
    long i,j,a,b,c,p,l=0;
    while(cin>>n)
    {
       cin>>m;
       for(i=1;i<=m;i++)
       {
          k[i]=0;
          for(j=1;j<=m;j++)
          {
          q[i][j]=0;
          qs[i][j]=0;
          }
       }
       for(i=1;i<=n;i++)
       {
          cin>>a>>b>>c;
          q[a][b]=q[a][b]+c;
       }
       for(i=1;i<=m;i++)
       {
          for(j=1;j<=m;j++)
          {
             cout<<q[i][j]<<" ";
          }
          cout<<endl;
       }
       k[1]=1;
       while(l>=0)
       {
          j=0;
          for(i=2;i<=m;i++)k[i]=0;
          for(i=1;i<=m;i++)
          {
             if(q[1][i]>0&&q[1][i]>qs[1][i])
             {
                k[i]=1;
                j=go(i,q[1][i]-qs[1][i]);
                qs[1][i]=qs[1][i]+j;
                s=s+j;
                cout<<i<<endl;
                if(j==0)continue;
                else break;
             }
             if(q[i][1]>0&&qs[i][1]>0)
             {
                k[i]=1;
                j=go(i,qs[i][1]);
                qs[1][i]=qs[1][i]-j;
                cout<<i<<" "<<j<<endl;
                s=s+j;
                if(j==0)continue;
                else break;
             }
          }
          l++;
          if(j==0)break;
       }
       cout<<s<<endl;
    }
    return 0;
}