#include<fstream.h>
#define nx 50005
#define inf 1<<30
struct g
 {
  int nod,cost;
  g *next;
 };
g *a[nx];
int Q[nx],n,m;
long d[nx];

void bellmanford()
 {
  int i,e=0,u=0,r,nr=1;
  for (i=1;i<=n;++i)
   d[i]=inf;
  d[1]=0;Q[0]=1;int inQ[nx]={0};
  inQ[1]=1;
  while (nr)
   {
    r=Q[e];
    e=(e+1)%n;
    nr--;
    inQ[r]=0;
    for (g *q=a[r];q;q=q->next)
      if (d[q->nod]>d[r]+q->cost)
    {
	d[q->nod]=d[r]+q->cost;
      if (!inQ[q->nod])
       {
	u=(u+1)%n;
	Q[u]=q->nod;
	inQ[q->nod]=1;
	++nr;
       }
    }
   }
 }

int main()
 {
  ifstream be ("dijkstra.in");
  ofstream ki ("dijkstra.out");
  be>>n>>m;
  int i,x,y,c;
  for (i=1;i<=m;++i)
   {
    be>>x>>y>>c;
    g *q=new g;
    q->nod=y;
    q->cost=c;
    q->next=a[x];
    a[x]=q;
   }
  be.close();
  bellmanford();
  for (i=2;i<=n;++i)
   {
    if (d[i]==inf)
     ki<<"0 ";
    else
     ki<<d[i]<<" ";
   }
  ki.close();
  return 0;
 }