#include <bits/stdc++.h>
using namespace std;
#define inf 20001
ifstream fin("dijkstra.in");
#define cin fin
ofstream fout("dijkstra.out");
#define cout fout
vector <pair <int, int>> v[50001];
set <pair <int, int>> s;
int z[50001], n, m, a, b, c, p;
bool viz[50001];
int main(){
    cin>>n>>m;
    for(int i=2; i<=n; i++) z[i]=inf;
    for(int i=0; i<m; i++){
        cin>>a>>b>>c;
        v[a].push_back(make_pair(b, c));
    }
    s.insert(make_pair(0, 1));
    int p, vc, cost;
    while(!s.empty()){
        p=s.begin()->second;
        s.erase(s.begin());
        for(int i=0; i<v[p].size(); i++){
            vc=v[p][i].first;
            cost=v[p][i].second;
            if(z[vc]>z[p]+cost){
                s.erase(make_pair(z[vc], vc));
                z[vc]=z[p]+cost;
                s.insert(make_pair(z[vc], vc));
            }
        }
    }
    for(int i=2; i<=n; i++){
        if(z[i]!=inf) cout<<z[i]<<' ';
        else cout<<'0'<<' ';
    }
    return 0;
}