#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];
int hs;

void up(int pos){
    if(pos==1) return;
    if(p[h[pos]]>=p[h[pos/2]]) return;
    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(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(h[pos],h[fiu]);
    down(fiu);
}

void del(int pos){
    h[pos]=0;
    swap(h[pos],h[hs]);
    hs--;
    if(pos==hs+1) return;
    if(pos!=1 || (p[h[pos]]<=p[h[2*pos]] && p[h[pos]]<=p[h[2*pos+1]])) up(pos);
    else down(pos);
}

void Dijkstra(){
    h[++hs]=1;
    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){
                h[++hs]=a[h[1]][i].first;
                p[h[hs]]=p[h[1]]+a[h[1]][i].second;
                up(hs);
            }
        }
        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] << ' ';
    }
}