#include <bits/stdc++.h>
#define INFINITE INT_MAX
#define MAX_N 100000
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct nod{
        int inf,c;
        nod *urm;
} *rel[MAX_N+1];
int d[MAX_N+1],dh,z;
int poz[MAX_N+1],h[MAX_N+1],n,m,vp;

void citire(){

        f>>n>>m;vp=1;
        dh=n;
        nod* q;
        for (int i=1,x,y,cst;i<=m;i++){
                f>>x>>y>>cst;
                q=new nod;
                q->inf=y;
                q->c=cst;
                q->urm=rel[x];
                rel[x]=q;
                //q=new nod;
                //q->inf=x;
                //q->c=cst;
                //q->urm=rel[y];
                //rel[y]=q;
        }
        for (int i=1;i<=n;i++){
                d[i]=INFINITE;
                //poz[i]=i;
                h[i]=i;//swap(h[1],h[vp]);
        }
        d[vp]=0;swap(h[1],h[vp]);
}


void Swap(int i,int j){
        int aux=h[i];h[i]=h[j];h[j]=aux;
        //poz[h[i]]=i;
        //poz[h[j]]=j;
}


void heap_dw(int i){
        int l=2*i,r=2*i+1,min=i;
        if (l<=dh && d[h[l]]<d[h[min]]){min=l;};
        if (r<=dh && d[h[r]]<d[h[min]]){min=r;};
        if (min!=i){
                Swap(i,min);
                heap_dw(min);
        }
}


void heap_up(int i){
        int dad=i/2;
        if (dad){
                if (d[h[i]]<d[h[dad]]){Swap(i,dad);heap_up(dad);}
        }
}


int extract_min(void){
        Swap(1,dh);
        dh--;
        heap_dw(1);
        return (h[dh+1]);
}


void dijkstra(void){
        dh=n; //int nmin=vp;Swap(vp,dh);dh--;heap_dw(n);//int nmin=h[dh+1];
        while (dh){
                int nmin=extract_min();
                for (nod *p=rel[nmin];p;p=p->urm)
                        if (d[p->inf]>d[nmin]+p->c){d[p->inf]=d[nmin]+p->c; heap_up(p->inf);}//heap_up(poz[p->inf]);}
                //nmin=extract_min();
               }
        for (int i=2;i<=n;i++) if (d[i]==INFINITE)g<<0<<" "; else if(i==vp) g<<0<<" "; else g<<d[i]<<" ";
}


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