#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define nl '\n'
#define sz(x) (int)x.size()
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define F0R(i, a, b) for (int i = a; i >= b; --i)
#define all(x) (x).begin(), (x).end()
#define trav(a,x) for (auto& a : x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
using namespace std;

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mxN = 5e4 + 5;

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

vector<pair<int, int>> edges[mxN];
int dist[mxN];

void solve() {
    int N, M; fin >> N >> M;
    FOR(i, 1, N + 1) dist[i] = INT_MAX;
    while (M--) {
        int x, y, z; fin >> x >> y >> z;
        edges[x].push_back({y, z});
    }
    set<pair<int, int>> s;
    dist[1] = 0;
    s.insert({0, 1});
    while (!s.empty()) {
        int curr = s.begin()->second;
        s.erase(s.begin());
        for (auto next : edges[curr]) {
            if (dist[next.first] > dist[curr] + next.second) {
                if (dist[next.first] != INT_MAX) {
                    s.erase(s.find({dist[next.first], next.first}));
                }
                dist[next.first] = dist[curr] + next.second;
                s.insert({dist[next.first], next.first});
            }
        }
    }
    FOR(i, 2, N + 1) {
        fout << (dist[i] == INT_MAX ? 0 : dist[i]) << " ";
    }
}

int main() {
    ios::sync_with_stdio(0), fin.tie(0), fout.tie(0);
    int T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}