#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <numeric>
#include <functional>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <memory>
#include <thread>
#include <tuple>
#include <limits>
#include <iostream>

using namespace std;

int n;
vector<vector<pair<int, int>>> graph;
int best_path[2001][2001];

long long calc(int start) {
  priority_queue<pair<long long, int>> pq;
  vector<long long> dist(n, LLONG_MAX);
  vector<char> visit(n, 0);
  pq.emplace(0, start);
  dist[start] = 0;
  while (!pq.empty()) {
    long long curdist;
    int cur;
    tie(curdist, cur) = pq.top();
    pq.pop();
    curdist = -curdist;
    if (visit[cur]) continue;
    for (auto edge : graph[cur]) {
      int next = edge.first;
      long long nd = edge.second + curdist;
      if (dist[next] > nd) {
        dist[next] = nd;
        pq.emplace(-nd, next);
      }
    }
  }
  long long ans = LLONG_MAX;
  for (int i = 0; i < n; i++) {
    if (dist[i] == LLONG_MAX)continue;
    if (best_path[i][start] == -1) continue;
    ans = min(ans, best_path[i][start] + dist[i]);
  }
  if (ans == LLONG_MAX) ans = -1;
  return ans;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int m;
  cin >> n >> m;
  for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) best_path[i][j] = -1;
  graph.resize(n);
  for (int i = 0; i < m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    a--, b--;
    graph[a].emplace_back(b, c);
    if (best_path[a][b] == -1 || best_path[a][b] > c) {
      best_path[a][b] = c;
    }
  }
  for (int i = 0; i < n; i++) {
    cout << calc(i) << "\n";
  }
  return 0;
}

#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep_inv(i, n, m) for(int i = (int)(n); i > (int)(m); i--)
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vc = vector<char>;
using vvl = vector<vl>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;

ll infty = (ll)pow(10, 15);

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

  map<pll, ll> loads;
  map<ll, vl> from;
  map<ll, vl> to;
  
  ll A, B, C;
  
  rep(i, M){
    cin >> A >> B >> C;

    if(loads.count({A, B}) == 1){ // 既に登録されていた場合、注意が必要
      loads[{A, B}] = min(loads[{A, B}], C);
    } else{
      loads[{A, B}] = C;
      from[A].push_back(B);
      to[B].push_back(A);
    }
  }

  rep2(i, 1, N + 1){
    if((from.count(i) == 0) || (to.count(i) == 0)){
      cout << -1 << "\n";
      continue;
    }

    vl dist(N + 1, infty);
    vl done(N + 1, 0);
    priority_queue<pll, vpll, greater<pll> > Q;

    dist[0] = 0;
    Q.push({0, 0});
    
    while(!Q.empty()){
      ll cost = Q.top().first;
      ll cnode = Q.top().second;
      Q.pop();

      if(cost > dist[cnode])
	continue;

      if(cnode == 0){
	for(auto itr = from[i].begin(); itr != from[i].end(); itr++){
	  if(dist[*itr] > loads[{i, *itr}] + dist[cnode]){
	    dist[*itr] = loads[{i, *itr}] + dist[cnode];
	    Q.push({dist[*itr], *itr});
	  }
	}
      } else{
	for(auto itr = from[cnode].begin(); itr != from[cnode].end(); itr++){
	  if(dist[*itr] > loads[{cnode, *itr}] + dist[cnode]){
	    dist[*itr] = loads[{cnode, *itr}] + dist[cnode];
	    Q.push({dist[*itr], *itr});
	  }
	}
      }
    }

    if(dist[i] < infty)
      cout << dist[i] << "\n";
    else
      cout << -1 << "\n";
  }
  
  return 0;
}
