#include<fstream>
#include<algorithm>
#include<iostream>
#include<vector>

using namespace std;

const int INF = 1000000000;

 ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");

struct QQ{
    int x,v;
};

const int NMAX=(1<<17);
typedef QQ Heap[NMAX];

int father(int k){
    return (k/2);
}

int left_son(int k){
    return (2*k);
}

int right_son(int k){
    return (2*k + 1);
}

void  sift(Heap h, int n , int k){
    int son = 0;

    do{
        son=0;
        if(left_son(k) <=n){

            son=left_son(k);
            if(right_son(k)<=n && h[right_son(k)].v < h[left_son(k)].v){
                son=right_son(k);
            }
            if(h[son].v>=h[k].v)
                son=0;

        }

        if(son){
            swap(h[son],h[k]);
            k=son;
        }

    }while(son);

}

void percolate(Heap h, int k){
    int key=h[k].v;
    int xx=h[k].x ;

    while((k>1) && (key<h[father(k)].v)){
       h[k]=h[father(k)];
        k=father(k);
    }

    h[k].v=key;
    h[k].x=xx;
}

void cut(Heap h, int &n, int k){
    h[k]=h[n];
    n--;

    if(k>1 && h[k].v<h[father(k)].v)
        percolate(h,k);
    else
        sift(h,n,k);
}

void inser(Heap h, int &n, int key, int x){
    n++;
    h[n].v=key;
    h[n].x=x;

    percolate(h,n);
}

void build(Heap h, int n){
    for(int i=n/2; i>0; --i)
        sift(h,n,i);
}


vector< pair<int, int> > a[50009];
vector<int> d(50009,INF);

int main(){


    int n,m,i,j,x,y,z,s=1,hsiz,nod,vl,to,ln;
    Heap h;

    f>>n>>m;
    for(i=1; i<=m; ++i){
        f>>x>>y>>z;
        a[x].push_back(make_pair(y,z));
    }


    d[s]=0;
    h[1].x=s;
    h[1].v=0;
    hsiz=1;

    while(hsiz>0){
        nod=h[1].x;

        cut(h,hsiz,1);


        for(i=0; i<a[nod].size(); ++i){
            to=a[nod][i].first;
            ln=a[nod][i].second;

            if(d[to] > d[nod] + ln ){
                d[to]=d[nod] +ln;

                inser(h,hsiz,d[to],to);

            }
        }
    }

     for(i=2; i<= n; ++i)
        if(d[i]==INF)
            g<<"0 ";
        else
            g<<d[i]<<' ';


return 0;
}