#include <fstream>

using namespace std;

const int maxn = 50001;
const int inf = 1<<30;


struct graf{

    int nod,cost;
    graf *next;

};

int n,m;
graf *a[maxn];
int d[maxn],h[maxn],poz[maxn],k;


void add(int where ,int what, int cost ){

    graf *q=new graf;

    q-> nod = what;
    q-> cost = cost;
    q-> next = a[where];
    a[where]= q;

}

void read(){
    ifstream fin("dijkstra.in");

    fin >> n>>m;
    int x,y,c;
    for(int i=0;i<m;i++){
        fin >> x>>y>>c;
        add(x,y,c);
    }
    fin.close();

}

void swap(int x,int y){

    int t=h[x];
    h[x]=h[y];
    h[y]=t;

}

void upheap(int what){
    int tata;
    while(what>1){
        tata=what >>1;
        if(d[h[tata]]>d[h[what]]){
            poz[h[tata]]=what;
            poz[h[what]]=tata;

            swap(tata, what);
            what=tata;
        }else what=1;
    }


}

void downheap(int what){

    int fiu;

    while(what<=k){
        if(what<<1<=k){
            fiu=what<<1;
            if((fiu+1<=k)&&(h[fiu]>h[fiu+1])){
               fiu++;
            }
            if(h[what]>h[fiu]){
                poz[h[fiu]]=what;
                poz[h[what]]=fiu;

                swap(fiu,what);
                what=fiu;

            }else return;


        }else return;

    }




}

void dijkstra_heap(){

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

    while(k){
        int min=h[1];
        swap(1,k);
        poz[h[1]]=1;
        k--;
        downheap(1);

        graf *q=a[min];
        while(q){
            if(d[q->nod]>d[min]+q-> cost){
                d[q->nod]=d[min]+q->cost;
                if(poz[q->nod]!=-1){
                    upheap(poz[q->nod]);
                }else{
                    h[++k]=q->nod;
                    poz[q->nod]=k;
                    upheap(k);

                }
            }
            q=q->next;
        }

    }








}


int main()
{
    read();
    dijkstra_heap();

    ofstream fout("dijkstra.out");

    for(int i=2;i<=n;i++){

        fout<<(d[i] == inf ? 0:d[i])<<" ";
    }
    fout<<'\n';
    fout.close();
    return 0;
}