#include <fstream>
#define infinit 1000000001
using namespace std;
ifstream  fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n, m, start[50002], k, x, y, c;
struct nod{
    int vecin,cost,leg;
}L[250002];
int d[50002],heapMin[50002],nh,posInHeap[50002];
char viz[50002];
void dijkstra(int p){
    for(int i=1;i<=n;i++){
        d[i]=infinit;
        viz[i]=0;
    }
    d[p]=0;
    heapMin[1]=p;
    nh=1;
    posInHeap[p]=1;
    for(int i=1;i<=n;i++){
        if(i!=p){
            nh++;
            heapMin[nh]=i;
            posInHeap[i]=nh;
        }
    }
    for(int r=1;r<=n;r++){
        ///caut cel mai mic cost al varfurilor nevizitate inca, deci din heap
        if(d[heapMin[1]]==infinit){
            ///graful nu este conex si nu mai putem continua
            break;
        }
        ///heapMin[1] este varful care ne da minimul
        x=heapMin[1];
        viz[x]=1;
        ///il scoatem/stergem din heap
        heapMin[1]=heapMin[nh];
        posInHeap[heapMin[1]]=1;
        nh--;
        ///coboram heapMin[1] la pozitia potrivita din heap
        y=1;
        while(y*2<=nh){
            int q=y*2;
            if(q+1<=nh && d[heapMin[q+1]]<d[heapMin[q]]){
                q=q+1;
            }
            if(d[heapMin[q]]<d[heapMin[y]]){
                int aux=heapMin[y];
                heapMin[y]=heapMin[q];
                heapMin[q]=aux;
                posInHeap[y]=q;
                posInHeap[q]=y;
                y=q;
            }
            else{
                break;
            }
        }
        ///relaxam informatiile vecinilor lui x
        for(int i=start[x];i!=0;i=L[i].leg){
            if(viz[L[i].vecin]==0 && d[x]+L[i].cost<d[L[i].vecin]){
                d[L[i].vecin]=d[x]+L[i].cost;
                ///deoarece am facut imbunatatiri va trebui sa actualizam si in heap
                ///L[i].vecin poate doar sa urce, deoarece are o valoare mai mica decat inainte
                y=posInHeap[L[i].vecin];///L[i].vecin se afla in heap la pozitia y
                while(y>=2 && d[heapMin[y/2]]>d[heapMin[y]]){
                    int aux=heapMin[y];
                    heapMin[y]=heapMin[y/2];
                    heapMin[y/2]=aux;
                    posInHeap[y]=y/2;
                    posInHeap[y/2]=y;
                    y=y/2;
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(i!=p){
            if(d[i]==infinit){
                fout<<0<<" ";
            }
            else{
                fout<<d[i]<<" ";
            }
        }
    }
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        fin>>x>>y>>c;
        k++;
        L[k]={y,c,start[x]};
        start[x]=k;
    }
    dijkstra(1);
    return 0;
}