#include <bits/stdc++.h>

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int S[50005],D[50005],T[50005];
int a[5005][5005];
int n,m;
const int inf=20005;
void Read()
{  fin>>n>>m;
   int x,y,c;
  for(int i=1;i<=m;i++)
  {
      fin>>x>>y>>c;
      a[x][y]=c;
  }

}
void Init()
{   for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
         if(i==j) a[i][j]=0;
         else a[i][j]=inf;

}
void Dj(int x)
{
    int imin,dmin;
    S[x]=1;
    for(int i=1;i<=n;i++)
    {
        D[i]=a[x][i];
        if(D[i]<inf) T[i]=x;
        else T[i]=0;
    }
    T[x]=0;
    for(int k=1;k<=n-1;k++)
    {
          dmin=inf+1;
        for(int i=1;i<=n;i++)
        if(D[i]<dmin && S[i]==0) {imin=i; D[i]=dmin;}
        S[imin]=1;

        for(int i=1;i<=n;i++)
        if(S[i]==0 && D[i]>a[imin][i]+D[imin])
        {

           D[i]=a[imin][i]+D[imin];  T[i]=imin;
        }


    }
    for(int i=2;i<=n;i++)
       {if(D[i]==inf) fout<<0<<" ";
        else fout<<D[i]<<" ";
       fout<<"\n";
       }


}


int main()
{   Init();
    Read();
    Dj(1);

    return 0;
}