#include <stdio.h>
#define DIM 50010
#define INF 2100000000

struct nod {
  int v;
  int c;
  nod *urm;
};

nod *pp[DIM],*q;

int poz[DIM],h[DIM],d[DIM];

int n,m,i,c,p,min,x,y,cost,k,aux,pz;

int main(){
  FILE *f = fopen("dijkstra.in","r");
  fscanf(f,"%d %d",&n,&m);
  for (i=1;i<=n;i++)
    pp[i]=NULL;
  for (i=1;i<=m;i++) {
    fscanf(f,"%d %d %d",&x,&y,&cost);
    q = new nod;
    q->v = y;
    q->c = cost;
    q->urm=pp[x];
    pp[x]=q;

  }
  fclose(f);

  for (i=2;i<=n;i++){
    d[i]=INF;
    poz[i]=-1;
  }
  d[1]=0;
  h[1]=1;
  poz[1]=1;
  k=1;
  while (k) {
    min = h[1];

    aux = h[k];
    h[k]=h[1];
    h[1]=aux;
    k--;
    poz[h[1]]=1;

    p=1;
    c=p<<1;
    while (c<=k) {
      if ((c+1<=k) && (d[h[c]]>d[h[c+1]]))
	c++;
      if (d[h[p]]>d[h[c]]) {
	aux = h[p];
	h[p]=h[c];
	h[c]=aux;
	poz[h[p]]=p;
	poz[h[c]]=c;
	p=c;
	c=c<<1;
      } else c=k+1;
    }

    q=pp[min];

    while (q!=NULL) {
      if (d[q->v]>d[min]+q->c) {
	d[q->v]=d[min]+q->c;
	if (poz[q->v]==-1) {
	  k++;
	  h[k]=q->v;
	  pz=k;
	  poz[q->v]=k;
	} else pz = poz[q->v];
	c = pz;
	p = c>>1;
	while (p>=1) {
	  if (d[h[p]]>d[h[c]]) {
	    aux = h[p];
	    h[p] = h[c];
	    h[c] = aux;
	    poz[h[p]]=p;
	    poz[h[c]]=c;
	    c=p;
	    p=p>>1;
	  } else p=0;
	}


      }


      q=q->urm;
    }

  }
  FILE *g = fopen("dijkstra.out","w");
  for (i=2;i<=n;i++)
    if (d[i]==INF)
      fprintf(g,"0 ");
    else
      fprintf(g,"%d ",d[i]);
  fclose(g);

  return 0;
}