#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];
pair<long long,long long> h[50000005];
int hs;

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

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

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

void Dijkstra(){
    h[++hs]={1,0};
    p[1]=0;
    while(hs){
        if(p[h[1].first]==h[1].second){
            for(int i=0;i<a[h[1].first].size();i++){
                if(p[a[h[1].first][i].first]>p[h[1].first]+a[h[1].first][i].second){
                    h[++hs]={a[h[1].first][i].first,p[h[1].first]+a[h[1].first][i].second};
                    p[h[hs].first]=p[h[1].first]+a[h[1].first][i].second;
                    up(hs);
                }
            }
            del(1);
        }
        else 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] << ' ';
    }
}