#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Node{
    int to;
    int d;
};
using graph = vector<vector<Node>>;

int main()
{
    int n, m;
    cin >> n >> m;
    graph g(n);
    for(int i=0; i<m; ++i){
        int a, b, c;
        cin >> a >> b >> c;
        g[a-1].push_back({b-1, c});
    }
    vector<vector<int>> d(n, vector<int>(n, 1e9));
    for(int i=0; i<n; ++i){
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push({0, i});
        while(!pq.empty()){
            auto [d_now, u] = pq.top();
            pq.pop();
            for(const auto &e: g[u]){
                if(d[i][e.to] > d_now + e.d){
                    d[i][e.to] = d_now + e.d;
                    pq.push({d[i][e.to], e.to});
                }
            }
        }
    }
    for(int i=0; i<n; ++i){
        int ans = d[i][i];
        if(ans == 1e9){
            cout << -1 << endl;
        }else{
            cout << ans << endl;
        }
    }
    return 0;
}
#include <bits/stdc++.h>
using namespace std;
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const long long LINF = 1LL << 60;

using Graph = vector<vector<pair<int, long long>>>;
int N, M;

vector<long long> dijkstra(const Graph &G, int s) {
    int min_v;
    vector<long long> dist(N, LINF);
    priority_queue<pair<long long, int>> pq;
    dist[s] = 0;
    pq.emplace(0, s);
    while (!pq.empty()) {
        min_v = pq.top().second; pq.pop();
        for (pair<int, long long> p : G[min_v]) {
            if (chmin(dist[p.first], dist[min_v] + p.second)) pq.emplace(-dist[p.first], p.first);
        }
    }
    return dist;
}

int main() {
    cin >> N >> M;
    Graph G(N), to(N);
    int A, B, C;
    rep(i, M) {
        cin >> A >> B >> C; A--; B--;
        G[A].emplace_back(B, C);
        to[B].emplace_back(A, C);
    }
    rep(i, N) {
        auto dist = dijkstra(G, i);
        long long res = LINF;
        for (auto [to, cost]: to[i]) chmin(res, dist[to] + cost);
        if (res != LINF) cout << res << endl;
        else cout << "-1" << endl;
    }
}
