#include <fstream>
#include<climits>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int i,D[1000],T[1000],S[1000],n,x,y,r,z,a[100][100],j,ok1,ok2,k,minim,v[1000],k1,m;
int main()
{fin>>n>>m;
for(i=1;i<=m;i++)
{fin>>x>>y>>z;
    a[x][y]=z;}
    r=1;
    for(i=1;i<=n;i++)
if(i!=r) {
    if(a[r][i]) D[i]=a[r][i];
    else D[i]=INT_MAX/2;
}
else D[i]=0;
S[r]=1;
for(i=1;i<=n;i++)
    if(a[r][i]) T[i]=r;
    else T[i]=0;
    for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
  if(!a[i][j]) a[i][j]=INT_MAX/2;
  while(ok1==0&&ok2==0)
  {minim=INT_MAX;
      for(i=1;i<=n;i++)
  if(S[i]==0) if(D[i]<minim) {minim=D[i];k=i;}
      S[k]=1;
      for(i=1;i<=n&&S[i]==0;i++)
        if(D[k]+a[k][i]<D[i]) {D[i]=D[k]+a[k][i];T[i]=k; }
        ok1=1; ok2=1;
  for(i=1;i<=n;i++)
  if(S[i]==0) {ok1=0; if(D[k]!=INT_MAX/2) ok2=0; }
  }

 /* for(i=1;i<=n;i++)
    fout<<T[i]<<' ';fout<<'\n';*/
    for(i=2;i<=n;i++)
    fout<<D[i]<<' ';fout<<'\n';
  /*for(i=1;i<=n;i++)
{k1=0;
    if(T[i]!=0){
    j=i;
//fout<<j<<' ';
v[++k1]=j;
    while(T[j]!=r)  {
            //fout<<T[j]<<' ';
            v[++k1]=T[j];
            j=T[j];}
            //fout<<T[j]<<' ';
             v[++k1]=T[j];
             for(j=k1;j>=1;j--)
                fout<<v[j]<<' ';
            fout<<'\n';
}
else fout<<"nu putem ajunge"<<'\n';
}*/
    return 0;
}