#include <stdio.h>
#define INF 2000000000
#define MAXN 500000
#define MAXM 250000
FILE *fin, *fout;

int k=1,v[MAXM+1],l[MAXM+1],next[MAXM+1],w[MAXN+1];
int d,h[MAXN+1],key[MAXN+1],e[MAXN+1],poz[MAXN+1];
bool viz[MAXN+1];

void downheap(int nod){
  int son=nod*2+1,aux;
  if(son+1<d && key[h[son+1]]<key[h[son]])
    son++;
  while(son<d && key[h[nod]]>key[h[son]]){
    aux=h[nod];
    h[nod]=h[son];
    h[son]=aux;
    poz[h[nod]]=nod;
    poz[h[son]]=son;
    nod=son;
    son=nod*2+1;
    if(son+1<d && key[h[son+1]]<key[h[son]])
      son++;
  }
}

void upheap(int nod){
    int parent=(nod-1)/2,aux;
    while(parent>=0 && key[h[nod]]<key[h[parent]]){
        aux=h[nod];
        h[nod]=h[parent];
        h[parent]=aux;
        poz[h[nod]]=nod;
        poz[h[parent]]=parent;
        nod=parent;
        parent=(nod-1)/2;
    }
}

void heapify(){
  int i;
  for(i=(d-1)/2; i>=0; i--)
    downheap(i);
}

void vecini(int nod){
  int i=v[nod];
  while(l[i]){
    if(!viz[l[i]] && key[nod]+w[i]<key[l[i]]){
      key[l[i]]=key[nod]+w[i];
      e[l[i]]=nod;
      upheap(poz[l[i]]);
    }
    i=next[i];
  }
}

int main(){
  FILE *fin=fopen("dijkstra.in","r");
  FILE *fout=fopen("dijkstra.out","w");
  int n,m,i,x,y,c;

  fscanf(fin,"%d%d",&n,&m);
  for(i=0; i<m; i++){
    fscanf(fin,"%d%d%d",&x,&y,&c);
    l[k]=y;
    w[k]=c;
    next[k]=v[x];
    v[x]=k++;
  }
  for(i=1; i<=n; i++){
    h[i-1]=i;
    poz[i]=i-1;
    key[i]=INF;
  }
  key[1]=0;
  viz[1]=1;
  d=n;
  heapify();
  while(d){
    int nod=h[0];
    h[0]=h[--d];
    downheap(0);
    viz[nod]=1;
    vecini(nod);
  }
  for(i=2; i<=n; i++)
    if(key[i]==INF)
      fprintf(fout,"0 ");
    else
      fprintf(fout,"%d ",key[i]);
  fclose(fin);
  fclose(fout);
  return 0;
}