#include <bits/stdc++.h>
#define Nmax 50050
#define INF (1 << 30)

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int N, dp[Nmax];
vector < pair < int, int > > L[Nmax];
priority_queue <pair <int, int> > q;
bool used[Nmax];

inline void Read() {
    int i, M, x, y, c;
    fin >> N >> M;
    for(i = 1; i <= M; i++) {
        fin >> x >> y >> c;
        L[x].push_back({y, c});
    }
    fin.close();
}

inline void Solve() {
    int i, cost, nod, nnod;
    for(i = 2; i <= N; i++)
        dp[i] = INF;
    dp[1] = 0;
    q.push({0, 1});
    while(!q.empty()) {
        nod = q.top().second;
        q.pop();
        if(!used[nod]) {
            used[nod] = 1;
            for(i = 0; i < L[nod].size(); i++) {
                nnod = L[nod][i].first;
                cost = L[nod][i].second;
                if(dp[nnod] > dp[nod] + cost) {
                    dp[nnod] = dp[nod] + cost;
                    q.push({-dp[nnod], nnod});
                }
            }
        }
    }
}

inline void Write() {
    int i;
    for(i = 2; i <= N; i++)
        if(dp[i] == INF) fout << "0 ";
        else fout << dp[i] << " ";
    fout << "\n";
    fout.close();
}

int main() {
    Read();
    Solve();
    Write();
    return 0;
}