#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define FOR(i, a, b) for (int i = a; i < (b); i++)
#define range(a) a.begin(), a.end()
#define endl "\n"
#define Yes() cout << "Yes" << endl
#define No() cout << "No" << endl
#define MP make_pair
using P = pair<int, int>;
const unsigned long long mod = 1e9 + 7;
const long long INF = 1LL<<60;
void chmin(long long &a, long long b) { if (a > b) a = b; }
void chmax(long long &a, long long b) { if (a < b) a = b; }

struct Edge {
    ll to;
    ll cost;
	Edge(ll to, ll cost) : to(to), cost(cost) {}
};

using Graph = vector<vector<Edge>>;
using _P = pair<long, int>;

/* dijkstra(G,s,dis)
    入力：グラフ G, 開始点 s
    計算量：O(|E|log|V|)
*/
vector<ll> dijkstra(const Graph &G, int s) {
	int N = G.size();
	vector<ll> dis(N, INF);
    priority_queue<_P, vector<_P>, greater<_P>> pq;  // 「仮の最短距離, 頂点」が小さい順に並ぶ
    dis[s] = 0;
    pq.emplace(dis[s], s);
    while (!pq.empty()) {
        _P p = pq.top();
        pq.pop();
        int v = p.second;	//v : 今見ている頂点
        if (dis[v] < p.first) {  // 最短距離で無ければ無視
            continue;
        }
        for (auto &e : G[v]) {
            if (dis[e.to] > dis[v] + e.cost) {  // 最短距離候補なら priority_queue に追加
                dis[e.to] = dis[v] + e.cost;
                pq.emplace(dis[e.to], e.to);
            }
        }
    }
	return dis;
}

int main(void){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//頂点数、変数
	int N, M;
	cin >> N >> M;

	Graph G(N);
	FOR(i,0,M){
		int a, b, w;
		cin >> a >> b >> w;
		--a;
		--b;
		G.at(a).push_back(Edge(b, w));
	}

	//ダイクストラ法
	FOR(i,0,N){
		auto dis = dijkstra(G, i);
		ll ans = INF;
		FOR(j,0,N){
			for(auto x : G.at(j)){
				//cout<<x.to<<" "<<i<<endl;
				if(x.to == i){
					ans = min(ans, x.cost + dis.at(j));
				}
			}
		}
		//結果出力
		if(ans != INF)
			cout << ans << endl;
		else
			cout << -1 << endl;
	}

	return 0;
}
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  vector<vector<pair<int, int>>> e(n);
  for (int i = 0; i < m; i++) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    e[a - 1].push_back({b - 1, c});
  }

  for (int i = 0; i < n; i++) {
    vector<int> d(n, -1);
    priority_queue<pair<int, int>> pq;
    pq.push({0, i});
    while (!pq.empty()) {
      pair<int, int> p = pq.top();
      pq.pop();
      if (d[p.second] == -1) {
        d[p.second] = -p.first;
        for (pair<int, int> q : e[p.second]) {
          if (d[q.first] == -1) {
            pq.push({p.first - q.second, q.first});
          }
        }
      }
    }

    int ans = -1;
    for (pair<int, int> p : e[i])
      if (p.first == i && (ans == -1 || p.second < ans))
        ans = p.second;
    for (int j = 0; j < n; j++) {
      if (j == i || d[j] < 0) continue;
      for (pair<int, int> p : e[j])
        if (p.first == i && (ans == -1 || p.second + d[j] < ans))
          ans = p.second + d[j];
    }
    printf("%d\n", ans);
  }

  return 0;
}