#include <fstream>
#include <queue>
using namespace std;

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

struct point{
    vector<pair<int, int>> V;
    int d;
};

point X[50005];
int F[50005];
int main() {
    int n, m;
    cin>>n>>m;
    for (int i=1; i<=m; i++) {
        int x, y, l;
        cin>>x>>y>>l;
        X[x].V.push_back({y, l});
    }
    priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> S;
    S.push({0, 1});
    while (!S.empty()) {
        int first=S.top().first;
        int second=S.top().second;
        S.pop();
        if (F[second]==1) continue;
        else {
            F[second]=1;
            for (int i=0; i<X[second].V.size(); i++) {
                S.push({first+X[second].V[i].second, X[second].V[i].first});
            }
        }
        X[second].d=first;
    }
    for (int i=2; i<=n; i++) cout<<X[i].d<<" ";
}