#define pbinfo
#define fl
//#define func

#ifdef pbinfo

#include <unordered_map>
#include <map>
#include <vector>
#include <cmath>
#include <set>
#include <queue>
#include <array>

#ifdef fl

#include <fstream>

#else
#include <iostream>
#include <iomanip>
#endif

#ifdef func
#include "header.hpp"
#endif

#else

#include <bits/stdc++.h>

#endif
using namespace std;
 
#define lld long long int
#define ulld unsigned long long int
#define sh short
#define lwbit(x) (x & (-x))
#define mod 1234567

#ifdef fl
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
#endif

class fentree {
    int *fen, n;
public:

    fentree (int nn) : n(nn) {
        fen = new int[nn + 1];
    }
    
    void updatemin(int i, int x) {
        for (int k = i; k <= n; k += lwbit(k))
            fen[k] -= x;
    }

    void updateplus(int i, int x) {
        for (int k = i; k <= n; k += lwbit(k))
            fen[k] += x;
    }

    int sum(int i) {
        int s{};
        for (int k = i; k > 0; k -= lwbit(k))
            s += fen[k];
        return s;
    }

    int binfen(int a) {
        int s, i;
        for (s = 1; s <= n; s <<= 1);
        for (i = 0; s; s >>= 1)
            if (i + s <= n && fen[i + s] <= a) {
                i += s;
                a -= fen[i];
                if (!a)
                    return i;
            }
        return -1;
    }
};

int n, m;
vector<pair<int, int>> g[50001];
priority_queue<pair<int, int>> q;
vector<int> d(50001, -2000000000);
//array<bool, 50001> f;

void dijkstra() {
    d[1] = 0;

    q.push(make_pair(0, 1));
    
    while (!q.empty()) {
        auto c = q.top();
        q.pop();

        for (auto nd : g[c.second]) {
            int rd = nd.first + c.first;

            if (rd > d[nd.second]) {
                d[nd.second] = rd;
                q.push(make_pair(rd, nd.second));
            }
        }
    }
}

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int a, b, x;
        cin >> a >> b >> x;
        g[a].push_back(make_pair(-x, b));
    }

    dijkstra();

    for (int i = 2; i <= n; ++i)
        cout << -d[i] << ' ';
    cout << '\n';
    
    return 0;
}