#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];
set <pair<long long,long long>> c;

void Dijkstra(){
    c.insert({0,1});
    p[1]=0;
    while(c.size()){
        for(int j=0;j<a[(*c.begin()).second].size();j++){
            int k=(*c.begin()).second;
            if(p[a[k][j].first]>p[k]+a[k][j].second){
                p[a[k][j].first]=p[k]+a[k][j].second;
                c.insert({p[a[k][j].first],a[k][j].first});
            }
        }
        c.erase(*c.begin());
    }
}

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] << ' ';
    }
}