#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <utility>
#include <vector>
#include <limits>
#include <cmath>
#include <queue>
#include <unordered_map>

typedef long long ll;
const auto llMax = std::numeric_limits<ll>::max();

typedef struct {
    ll a; // from
    ll b; // to
    ll c; // time
} Route;


ll search(const int n, const std::vector<Route> r, int start, ll minTime)
{
    std::vector<ll> t(n, llMax);

    // make index
    std::vector<ll> index(n + 1, llMax);
    index[0] = 0;
    index[n] = r.size();
    for (ll i = 0; i < r.size(); i++) {
        ll a = r[i].a;
        index[a] = std::min(index[a], i);
    }
    for (ll i = n; i >= 0; i--) {
        if (index[i] == llMax) {
            index[i] = index[i + 1];
        }
    }

    t[start] = 0;
    std::queue<ll> pos;
    pos.push(start);
    while(!pos.empty()) {
        ll now = pos.front();
        pos.pop();

        for (ll i = index[now]; i < index[now + 1]; i++) {
            Route nowRoute = r[i];
            const ll time = t[now] + nowRoute.c;
            if (time > minTime) {continue;}
            if (nowRoute.b == start) {
                minTime = time;
                continue;
            }
            if (time < t[nowRoute.b]) {
                t[nowRoute.b] = time;
                pos.push(nowRoute.b);
            }
        }
    }

    return minTime;
}

int main(int argc, char *argv[])
{
    ll n, m;
    std::vector<Route> r;

    std::cin >> n >> m;
    r.reserve(m);

    std::vector<ll> loopTime(n, llMax);

    for (int i = 0; i < m; i++) {
        ll a, b, c;
        std::cin >> a >> b >> c;
        a--; b--;

        if (a == b) {
            loopTime[a] = std::min(loopTime[a], c);
        } else {
            r.push_back({a, b, c});
        }
    }

    std::sort(r.begin(), r.end(), [](auto const& lhs, auto const& rhs){
        return lhs.a < rhs.a;
    });

    for (int i = 0; i < n; i++) {
        ll time = search(n, r, i, loopTime[i]);
        ll ans = (time != llMax) ? time : -1;
        std::cout << ans << std::endl;
    }

    return 0;
}

#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <numeric>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

#define rep(i, N) for(int i = 0; i < N; ++i)

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

#define IN(l, r, x) ((l) <= (x) && (x) < (r))

using P = pair<s64, s64>;

void dijkstra(const vector< vector< P > >& g, vs64& d, int s)
{
    static const s64 INF = 1e18;
    rep (i, d.size()) d[i] = INF;
    d[s] = 0;

    priority_queue< P, vector<P>, greater<P> > pq;
    pq.push(P{d[s], s});
    while (!pq.empty())
    {
        auto p = pq.top(); pq.pop();
        int from = p.second;
        s64 d1 = p.first;
        if (d[from] < d1) continue;
        for (auto e : g[from])
        {
            int to = e.first;
            s64 d2 = e.second;
            if (d[to] > d1 + d2)
            {
                d[to] = d1 + d2;
                pq.push(P{d[to], to});
            }
        }
    }
}

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

    int n, m;
    cin >> n >> m;

    vector< vector< P > > g1(n);
    vector< vector< P > > g2(n);
    vs64 ans(n, (s64)1e18);
    rep (i, m)
    {
        int u, v;
        s64 c;
        cin >> u >> v >> c;
        --u, --v;
        g1[u].push_back(P{v, c});
        g2[v].push_back(P{u, c}); // reverse
        if (u == v) ans[u] = min(ans[u], c);
    }

    rep (i, n)
    {
        vs64 d1(n), d2(n);
        dijkstra(g1, d1, i);
        dijkstra(g2, d2, i);
        rep (j, n)
        {
            if (i == j) continue;
            ans[i] = min(ans[i], d1[j] + d2[j]);
        }
        if (ans[i] == (s64)1e18) ans[i] = -1;
        cout << ans[i] << "\n";
    }

    return 0;
}

