#include<bits/stdc++.h>

using namespace std;

#define LL long long
#define DD double
#define Pb push_back
#define Bp pop_back
#define Pf push_front
#define Fp pop_front
#define Ub upper_bound
#define Lb lower_bound
#define Bs binary_search
#define In insert
#define Mp make_pair
#define All(x) x.begin(), x.end()
#define mem(a, b) memset(a, b, sizeof(a))
#define fast ios_base::sync_with_stdio(0);cin.tie(0)
#define X first
#define Y second

const int mx1 = 35;
const int mx2 = 105;
const int mx3 = 2005;
const int mx4 = 10005;
const int mx5 = 200005;
const int mx6 = 1000005;

typedef vector<int> Vi;
typedef vector<DD> Vd;
typedef vector<bool> Vb;
typedef vector<Vi> VVi;
typedef pair<int, int> Pii;
typedef pair<DD, DD> Pdd;
typedef vector<Pii> Vpi;
typedef vector<Pdd> Vpd;
typedef queue<int> Qi;
typedef stack<int> Si;
typedef deque<int> Di;

int _toggle(int N, int pos) {return N = N ^ (1 << pos);}
int _set(int N, int pos) {return N = N | (1 << pos);}
int _reset(int N, int pos) {return N = N & ~(1 << pos);}
bool _check(int N, int pos) {return (bool)(N & (1 << pos));}
bool _upper(char a) {return a >= 'A' && a <= 'Z';}
bool _lower(char a) {return a >= 'a' && a <= 'z';}
bool _digit(char a) {return a >= '0' && a <= '9';}

int dx[] = {1, -1, 0, 0, -1, -1, 1, 1};
int dy[] = {0, 0, 1, -1, -1, 1, -1, 1};

///******************************************************///

const int inf = 1e9;
int n, m, a[mx3][mx3], self[mx3], dist[mx3][mx3];
Vpi g[mx3];

void dijkstra(int sr)
{
    priority_queue<Pii, vector<Pii>, greater<Pii>> Q;
    for(int i = 1; i <= n; i++){
        dist[sr][i] = a[sr][i];
        if(a[sr][i] < inf){
            Q.push({a[sr][i], i});
        }
    }
    while(!Q.empty()){
        int v = Q.top().Y;
        int d_v = Q.top().X;
        Q.pop();
        if(d_v != dist[sr][v]){
            continue;
        }
        for(auto i: g[v]){
            int to = i.X;
            int len = i.Y;
            if(dist[sr][v] + len < dist[sr][to]){
                dist[sr][to] = dist[sr][v] + len;
                Q.push({dist[sr][to], to});
            }
        }
    }
}

void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            a[i][j] = inf;
        }
        self[i] = inf;
    }
    for(int i = 1; i <= m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        if(u == v){
            self[u] = min(self[u], w);
        }
        else{
            a[u][v] = min(a[u][v], w);
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(a[i][j] < inf){
                g[i].Pb({j, a[i][j]});
            }
        }
    }
    for(int i = 1; i <= n; i++){
        dijkstra(i);
        int ans = min(dist[i][i], self[i]);
        if(ans == inf){
            ans = -1;
        }
        cout << ans << '\n';
    }
}

int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    fast;
    int tc = 1;
    //cin >> tc;
    while(tc--){
        solve();
    }
}

#include <bits/stdc++.h>
/* #include <atcoder/all> */

#define rng(i, a, b) for (int i = int(a); i < int(b); i++)
#define rep(i, b) rng(i, 0, b)
#define gnr(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define per(i, b) gnr(i, 0, b)

using namespace std;
/* using namespace atcoder; */

using ll = long long;
using P = pair<int, int>;

const ll INF = 1 << 30;

template<class T>
inline bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

struct Data {
  int to;
  ll cost;
};

int main() {
  int n, m;
  cin >> n >> m;
  vector<ll> dist(n, INF);
  vector<vector<ll>> G2(n, vector<ll>(n, INF));
  vector<vector<Data>> G(n, vector<Data>());
  rep(i, m) {
    int a, b;
    ll c;
    cin >> a >> b >> c;
    a--;
    b--;
    if (a == b) {
      chmin(dist.at(a), c);
    } else {
//      chmin(G2.at(a).at(b), c);
      Data d = {b, c};
      G.at(a).push_back(d);
    }
  }
//  vector<vector<Data>> G(n, vector<Data>());
//  rep(i, n) {
//    rep(j, n) {
//      if (i == j) continue;
//      Data d = {j, G2.at(i).at(j)};
//      G.at(i).push_back(d);
//    }
//  }

  vector<vector<ll>> dist2(n, vector<ll>(n, INF));
  rep(i, n) {
    vector<ll> dist3(n, INF);
    dist3.at(i) = 0;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>,
        greater<pair<ll, int>>> que;
    que.push(make_pair(dist3.at(i), i));
    while (!que.empty()) {
      int v = que.top().second;
      ll d = que.top().first;
      que.pop();
      if (d > dist3.at(v)) continue;
      for (auto e : G.at(v)) {
        if (e.to == i) {
          continue;
        }
        if (chmin(dist3.at(e.to), dist3.at(v) + e.cost)) {
          que.push(make_pair(dist3.at(e.to), e.to));
        }
      }
    }
    rep(j, n) {
//      cerr << dist3.at(j) << " ";
      dist2.at(i).at(j) = dist3.at(j);
    }
//    cerr << endl;
  }
  rep(i, n) {
    rep(j, n) {
      if (i == j) continue;
      dist.at(i) = min(dist.at(i), dist2.at(i).at(j) + dist2.at(j).at(i));
    }
  }
  rep(i, n) {
    cout << ((dist.at(i) == INF) ? -1 : dist.at(i)) << endl;
  }
  return 0;
}
