#include<bits/stdc++.h>
#define N 50010
#define pii pair<int,int>
#define x first
#define y second

using namespace std;

const int inf=1e9;
int n,m;
vector<pii>V[N];
int d[N];
set<pii>S;

int main() {
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    cin>>n>>m;
    for (int i=1; i<=m; ++i) {
        int x,y,c; cin>>x>>y>>c;
        V[x].push_back({y,c});
    }

    for (int i=1; i<=n; ++i) d[i]=inf;
    for (auto it:V[1]) d[it.x]=it.y, S.insert({it.y,it.x});
    while (S.size()) {
        int x=S.begin()->y;
        int c=S.begin()->x;
        S.erase(S.begin());
        for (auto it:V[x]) {
            if (d[it.x]>c+it.y) {
                d[it.x]=c+it.y;
                S.insert({c+it.y,it.x});
            }
        }
    }
    for (int i=2; i<=n; ++i) {
        if (d[i]==inf) cout<<0<<" ";
        else cout<<d[i]<<" ";
    }

    return 0;
}