#include<fstream.h>
#define inf 50000
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");


int a[inf][inf],n,m,t[inf],v[inf],d[inf];

void citire()
{int i,j,x,y,c;
 fin>>n>>m;
 for(i=1;i<=n;i++)
 for(j=i+1;j<=n;j++)
 a[i][j]=inf;
 for(i=1;i<=m;i++)
 {fin>>x>>y>>c;
  a[x][y]=c;
  }
 for(i=1;i<=n;i++)
 {d[i]=a[1][i];
  if(d[i]<inf) t[i]=1;
  }
 }



/*void drum(int i)
{
 if(t[i]) drum(t[i]);
 fout<<i<<" ";
 }*/


void afisare()
{int i;
 for(i=2;i<=n;i++)
 if(t[i])
 /*{fout<<"costul min de la 1 la "<<i<<": "<<d[i];
  fout<<"\n";
  drum(i);
  fout<<"\n";
  }
  else fout<<"nu exista drum de la 1 la "<<i<<"\n";
 } */
 fout<<d[i]<<" ";
 }

int main()
{int i,j,min,imin=0;
 citire();
 for(i=1;i<n;i++)
 {min=inf;
  for(j=1;j<=n;j++)
  if(v[i]==0 && d[i]<min)
  {min=d[i];
   imin=i;
   }
  v[imin]=1;
 for(j=1;j<=n;j++)
 if(v[j]==0 && d[j]>d[imin]+a[imin][j])
  {d[j]=d[imin]+a[imin][j];
   v[j]=1;
   t[j]=imin;
   }
 }
 afisare();
 fin.close();
 fout.close();
 return 0;
 }