#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <unordered_map>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

vector<int> g[2010];
vector<int> w[2010];
const int MX = 1e9;

int d[2010];

struct node {
    int u;
    int dd;
    node(int _u) {
        u = _u;
        dd = d[u];
    }
};

int visit[2010];

bool operator<(const node& a, const node& b) {
    return a.dd > b.dd;
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a].push_back(b);
        w[a].push_back(c);
    }
    
    for (int s = 1; s <= n; ++s) {
        //printf("src=%d\n", s);
        priority_queue<node> q;
        for (int i = 1; i <= n; ++i) {
            d[i] = MX;
            visit[i] = 0;
        }
        for (int j = 0; j < g[s].size(); ++j) {
            d[g[s][j]] = min(d[g[s][j]], w[s][j]);
        }
        for (int j = 0; j < g[s].size(); ++j) {
            q.push(node(g[s][j]));
        }
        while (!q.empty() && !visit[s]) {
            node cur = q.top();
            int x = cur.u;
            //printf(" x=%d\n", x);
            q.pop();
            if (visit[x]) continue;
            visit[x] = 1;
            //printf("  visit x=%d d[x]=%d\n", x, d[x]);
            for (int j = 0; j < g[x].size(); ++j) {
                int y = g[x][j];
                if (!visit[y]) {
                    if (d[x] + w[x][j] < d[y]) {
                        d[y] = d[x] + w[x][j];
                        q.push(node(y));
                        //printf("    relax y=%d d[y]=%d\n", y, d[y]);
                    }
                }
            }
        }
        if (visit[s]) {
            printf("%d\n", d[s]);
        } else {
            printf("-1\n");
        }
    }
}

#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;
}