#include <bits/stdc++.h>

using namespace std;

long long n,m,x,y,z;
vector <pair<long long,long long>> a[50005];
long long p[50005];
int h[50005],e[50005];
int hs;
int ch;

void up(int pos){
    if(pos==1) return;
    if(p[h[pos]]>=p[h[pos/2]]) return;
    swap(e[h[pos]],e[h[pos/2]]);
    swap(h[pos],h[pos/2]);
    up(pos/2);
}

void down(int pos){
    if(2*pos>hs) return;
    if(2*pos==hs){
        if(p[h[pos]]>p[h[2*pos]]) swap(e[h[pos]],e[h[2*pos]]), swap(h[pos],h[2*pos]);
        return;
    }
    if(p[h[pos]]<=p[h[2*pos]] && p[h[pos]]<=p[h[2*pos+1]]) return;
    int fiu;
    if(p[h[2*pos]]<=p[h[2*pos+1]]) fiu=2*pos;
    else fiu=2*pos+1;
    swap(e[h[pos]],e[h[fiu]]);
    swap(h[pos],h[fiu]);
    down(fiu);
}

void place(int pos){
    if(pos!=1 && (p[h[pos]]<=p[h[2*pos]] && p[h[pos]]<=p[h[2*pos+1]])) up(pos);
    else down(pos);
}

void del(int pos){
    swap(e[h[pos]],e[h[hs]]);
    swap(h[pos],h[hs]);
    e[h[hs]]=0;
    h[hs]=0;
    hs--;
    if(pos==hs+1) return;
    place(pos);
}

void Dijkstra(){
    h[++hs]=1;
    e[1]=hs;
    p[1]=0;
    while(hs){
        for(int i=0;i<a[h[1]].size();i++){
            if(p[a[h[1]][i].first]>p[h[1]]+a[h[1]][i].second){
                if(!e[a[h[1]][i].first]){
                    h[++hs]=a[h[1]][i].first;
                    p[h[hs]]=p[h[1]]+a[h[1]][i].second;
                    e[a[h[1]][i].first]=hs;
                    up(hs);
                }
                else{
                    h[e[a[h[1]][i].first]]=a[h[1]][i].first;
                    p[h[e[a[h[1]][i].first]]]=p[h[1]]+a[h[1]][i].second;
                    place(e[a[h[1]][i].first]);
                }
            }
        }
        del(1);
    }
}

int main()
{
    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");
    in >> n >> m;
    for(int i=1;i<=m;i++){
        in >> x >> y >> z;
        a[x].push_back({y,z});
    }
    for(int i=1;i<=n;i++) p[i]=100000000000;
    Dijkstra();
    for(int i=2;i<=n;i++) {
        if(p[i]==100000000000) p[i]=0;
        out << p[i] << ' ';
    }
}