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

void bellmanford()
 {
  int i,e=1,v=1,r;
  for (i=1;i<=n;++i)
   d[i]=inf;
  d[1]=0;Q[1]=1;int inQ[mx]={0};
  inQ[1]=1;
  while (e<=v)
   {
    r=Q[e++];
    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])
       {
	Q[++v]=q->nod;
	inQ[q->nod]=1;
       }
     }
   }
 }

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;
 }