#include<bits/stdc++.h>
#define rep(i,n,m) for(int i = (n); i <(m); i++)
#define rrep(i,n,m) for(int i = (n) - 1; i >=(m); i--)
#define DEBUG
#if defined DEBUG
    #define TRACE( format, ... )   printf( "%d\t" format, __LINE__, __VA_ARGS__ )
    #define TRACES( format, ... )   printf( "%d\t:" format, __LINE__)
#else
    #define TRACE( format, ... )
    #define TRACES( format, ... )
#endif
using namespace std;
using ll = long long;

const ll INF = 1e17;

int main()
{
    int N, M;
    cin >> N >> M;

    vector<vector<pair<int, ll>>> edges(2*N);
    for (int i=0; i<M; ++i) {
        int A, B, C;
        cin >> A >> B >> C;
        --A, --B;

        edges[A].emplace_back(B, C);
        edges[A].emplace_back(B+N, C);
        edges[A+N].emplace_back(B+N, C);
    }

    for (int i=0; i<N; ++i) {
        // printf("------%d %d\n", i, N);
        priority_queue<pair<ll, int>> pque;
        vector<ll> costs(2*N, INF);
        pque.emplace(0, i);
        int ans = -1;
        while (!pque.empty()) {
            int now;
            ll cost;
            tie(cost, now) = pque.top();
            pque.pop();
            cost *= -1;
            // printf("%lld %d\n", cost, now);

            if (now == i+N) {
                ans = cost;
                break;
            }

            if (cost >= costs[now]) continue;
            costs[now] =  cost;

            for (auto nxt: edges[now]) {
                ll next_cost = nxt.second + cost;
                if (costs[nxt.first] <= next_cost) continue;
                pque.emplace(-next_cost, nxt.first);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
using ll = long long;
using P = pair<int,int>;
using edge = struct { int to; int cost; };
const int INF = 1e9;

int n,m;
vector<int> a,b,c;
vector<vector<edge>> g;

void solve(int s) {
  vector<int> d(n+5, INF);
  priority_queue<P, vector<P>, greater<P>> que;
  d[s] = 0;
  que.push(P(0, s));

  while (!que.empty()) {
    P p = que.top(); que.pop();
    int v = p.second;
    if (d[v] < p.first) continue;

    REP(i,g[v].size()) {
      edge e = g[v][i];
      if (d[e.to] > d[v] + e.cost) {
        d[e.to] = d[v] + e.cost;
        que.push(P(d[e.to], e.to));
      }
    }
  }

  int ans = INF;
  REP(i,n) {
    if (d[i] == INF) continue;
    for(auto x: g[i]) {
      if (x.to == s) {
        ans = min(ans, d[i] + x.cost);
      }
    }
  }

  cout << (ans == INF ? -1 : ans) << endl;
  return;
}

int main() {
  cin >> n >> m;
  a.resize(m);
  b.resize(m);
  c.resize(m);
  g.resize(n);
  REP(i,m) {
    cin >> a[i] >> b[i] >> c[i];
    a[i]--; b[i]--;
    edge e = { b[i], c[i] };
    g[a[i]].emplace_back(e);
  }

  REP(i,n) solve(i);
  return 0;
}