    #include <bits/stdc++.h>
    using namespace std;
    int main(){
      int N, M;
      cin >> N >> M;
      vector<vector<pair<int, int>>> E(N);
      for (int i = 0; i < M; i++){
        int A, B, C;
        cin >> A >> B >> C;
        A--;
        B--;
        E[A].push_back(make_pair(C, B));
      }
      for (int i = 0; i < N; i++){
        vector<int> d(N, -1);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push(make_pair(0, i));
        while (!pq.empty()){
          int dd = pq.top().first;
          int v = pq.top().second;
          pq.pop();
          if (d[v] == -1){
            if (dd > 0){
              d[v] = dd;
            }
            for (auto P : E[v]){
              int w = P.second;
              if (d[w] == -1){
                pq.push(make_pair(dd + P.first, w));
              }
            }
          }
        }
        cout << d[i] << endl;
      }
    }
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(),v.end()
#define MP make_pair
#define MT make_tuple
typedef int64_t ll;
#define PA pair<ll,ll>
#define TU tuple<ll,ll,ll>
#define vi vector<ll>
#define vii vector<vector<ll> >
#define rep(i,n) for(ll (i)=0; (i)<(ll)(n); (i)++)
#define rep2(i,m,n) for(ll (i)=(m); (i)<(ll)(n); (i)++)
const ll INF = 1ll<<30;
const ll INF2 = 1ll<<32;

ll n,m;
vector<vector<PA>> graph;
vector<vector<PA>> graph_r;
vi self;
vi dist;
vi dist_r;

void dijkstra(vector<vector<PA>> &graph, ll sta, vi &dist) {
  priority_queue<PA,vector<PA>,greater<PA>> pq;
  pq.push(MP(0,sta));
  dist.at(sta) = 0;
  while(!pq.empty()) {
    PA state = pq.top();
    pq.pop();
    if(dist.at(state.second) < state.first) continue;
    for(auto nv: graph.at(state.second)) {
      if(dist.at(nv.first) > dist.at(state.second) + nv.second) {
        dist.at(nv.first) = dist.at(state.second) + nv.second;
        pq.push(MP(dist.at(state.second) + nv.second,nv.first));
      }
    }
  }
  
}


int main() {
  cin >>n>>m;
  graph.assign(n,vector<PA>(0));
  graph_r.assign(n,vector<PA>(0));
  
  self.assign(n,INF);
  ll a,b,c;
  rep(i,m) {
    cin >>a>>b>>c;
    if(a==b) self.at(a-1) = min(self.at(a-1),c);
    else {
      graph.at(a-1).push_back(MP(b-1,c));
      graph_r.at(b-1).push_back(MP(a-1,c));
    }
  }
  
  rep(sta,n) {
    dist.assign(n,INF);
    dist_r.assign(n,INF);
    dijkstra(graph, sta, dist);
    dijkstra(graph_r, sta, dist_r);
    vi dist_all(n);
    rep(i,n) dist_all.at(i) = dist.at(i) + dist_r.at(i);
    ll mini = INF2;
    rep(i,n) {
      if(i!= sta) mini = min(mini,dist_all.at(i));
    }
    mini = min(self.at(sta),mini);
    if(mini<INF) cout << mini << endl;
    else cout << -1 << endl; 
    
  }
  
}