#include <fstream>

std::ifstream fin("dijkstra.in");
std::ofstream fout("dijkstra.out");

template < class array_node >
class array{
private:
    array_node *p;
    int n,c;
    void double_size(){
        if(c!=0){
            array_node *q=new array_node[c*2];
            for(int i=0;i<n;i++){
                q[i]=p[i];
            }
            delete[] p;
            p=q;
            c*=2;
        }else{
            c=1;
            p=new array_node[c];
        }
    }
public:
    array(){
            p=nullptr;
            n=0;
            c=0;
        }
    array(int x, array_node y){
        p=new array_node[x];
        n=x;
        c=x;
        for(int i=0;i<n;i++){
            p[i]=y;
        }
    }
    ~array(){
        delete[] p;
    }
    int get_size(){
        return n;
    }
    void set_size(int x){
        if(x<=c){
            n=x;
        }else if(x<=c*2){
            double_size();
            n=x;
        }else{
            array_node *q=new array_node[x];
            for(int i=0;i<n;i++){
                q[i]=p[i];
            }
            delete[] p;
            p=q;
            c=x;
            n=x;
        }
    }
    void set_size(int x, array_node y){
        int oldn=n;
        set_size(x);
        for(int i=oldn;i<x;i++){
            p[i]=y;
        }
    }
    void push_back(array_node x){
        if(n==c){
            double_size();
        }
        p[n]=x;
        n++;
    }
    void pop_back(){
        n--;
    }
    void shrink(){
        if(c!=n){
            int *q=new array_node[n];
            for(int i=0;i<n;i++){
                q[i]=p[i];
            }
            delete[] p;
            p=q;
            c=n;
        }
    }
    void operator =(array &other){
        set_size(other.n);
        for(int i=0;i<n;i++){
            p[i]=other[i];
        }
    }
    array_node& operator [](int x){
        return p[x];
    }
};

template <class heap_node>
class heap{
private:
    array <heap_node> a;
public:
    heap(){}
    ~heap(){}
    void push(heap_node x){
        a.push_back(x);
        int p=a.get_size();
        while(p>1&&a[p-1]<a[p/2-1]){
            heap_node aux=a[p/2-1];
            a[p/2-1]=a[p-1];
            a[p-1]=aux;
            p/=2;
        }
    }
    void pop(){
        int n=a.get_size()-1;
        a[0]=a[n];
        a.pop_back();
        int p=1;
        while( ( p*2<=n && a[p-1]>a[p*2-1] ) || ( p*2+1<=n && a[p-1]>a[p*2] ) ){
            if(p*2+1>n||a[p*2-1]<a[p*2]){
                heap_node aux=a[p-1];
                a[p-1]=a[p*2-1];
                a[p*2-1]=aux;
                p*=2;
            }else{
                heap_node aux=a[p-1];
                a[p-1]=a[p*2];
                a[p*2]=aux;
                p=p*2+1;
            }
        }
    }
    heap_node top(){
        return a[0];
    }
    bool is_empty(){
        return a.get_size()>0;
    }
};

struct str{
    int x,y;
    bool operator <(str other){
        return y<other.y;
    }
    bool operator >(str other){
        return y>other.y;
    }
};

str make_str(int x, int y){
    str aux;
    aux.x=x;
    aux.y=y;
    return aux;
}

const int nmax=50000;

array <str> g[nmax+1];

heap <str> h;

int d[nmax+1];

int main(){
    int n,m;
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,z;
        fin>>x>>y>>z;
        g[x].push_back(make_str(y,z));
    }
    h.push(make_str(1,1));
    d[1]=1;
    while(h.is_empty()!=0){
        int x=h.top().x;
        int y=h.top().y;
        h.pop();
        if(d[x]==y){
            for(int i=0;i<g[x].get_size();i++){
                int xn=g[x][i].x;
                int yn=g[x][i].y;
                if(d[xn]==0||d[xn]>yn+y){
                    d[xn]=yn+y;
                    h.push(make_str(xn,d[xn]));
                }
            }
        }
    }
    for(int i=2;i<=n;i++){
        if(d[i]>0)
            fout<<d[i]-1<<" ";
        else
            fout<<0<<" ";
    }
    return 0;
}