#include <ctype.h>
#include <stdio.h>
using namespace std;
const int BUF_SIZE=4096;
const int N=50001, M=100002;
const int INF= 1<<30;

char buf[BUF_SIZE];
int pos=BUF_SIZE;
int d[N],vf[M],cost[M],nr,n,m,lst[N],urm[M];
bool viz[N];
int h[2*N],poz[N],k;


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

    }


}

inline char getChar(FILE *f) {
  if (pos == BUF_SIZE) {
    fread(buf, 1, BUF_SIZE, f);
    pos = 0;
  }
  return buf[pos++];
}

inline int read(FILE *f) {
  int result = 0;
  char c;
  do {
    c = getChar(f);
  } while (!isdigit(c));

  do {
    result = 10 * result + c - '0';
    c = getChar(f);
  } while (isdigit(c));

  return result;
}

void adauga(int x, int y, int c){
    nr++;
    vf[nr]=y;
    urm[nr]=lst[x];
    cost[nr]=c;
    lst[x]=nr;

}
void citire(){
    FILE *in;
    in=fopen("dijkstra.in","r");

    fscanf(in,"%d%d",&n,&m);
    int a,b,c;
    for(int i=1;i<=m;i++){
        a=read(in);b=read(in);c=read(in);
        adauga(a,b,c);
    }

}

void schimba(int x, int y){
    int t=h[x];
    h[x]=h[y];
    h[y]=t;

}

void avanseaza(int x){
     int parinte;
     while(x>1){
        parinte=x>>1;

        if( d[ h[parinte]]>d[h[x]]){
            poz[h[x]]=parinte;
            poz[h[parinte]]=x;
            schimba(parinte,x);
            x=parinte;

        }
        else x=1;
     }
}

void coboara(int x){
    int f;
    while(x<=k){
        f=x;
        if((x<<1)<=k){
            f=x<<1;
            if(f+1<=k){
                if(d[h[f+1]]<d[h[f]]) f++;
            }
        }
        else return;

        if(d[h[x]]>d[h[f]]){
            poz[h[x]]=f;
            poz[h[f]]=x;

            schimba(x,f);
            x=f;
        }
        else return;

        }
}


void dijkstra(){
    for(int i=2;i<=n;i++){
        d[i]=INF;
        poz[i]=-1;
    }
    poz[1]=1;
    h[++k]=1;

    while(k){
        int minim=h[1];
        schimba(1,k);
        poz[h[1]]=1;
        k--;
        coboara(1);

        int p=lst[minim],y;
        while(p){
            y=vf[p];

            if(d[y]>d[minim]+cost[p]){
                d[y]=d[minim]+cost[p];

                if(poz[y]!=-1){
                    avanseaza(poz[y]);
                }
                else{
                    h[++k]=y;
                    poz[h[k]]=k;
                    avanseaza(k);
                }
            }

            p=urm[p];
        }
    }
}

int main()
{
    citire();
    dijkstra();
    afisare();
    return 0;
}