#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)

using P = pair<int,int>;
using Edge = struct { int to; int cost; };
const int INF = 1e9;

vector<int> a,b,c;
int n,m;

// s: スタート位置, g: 隣接リストグラフ
vector<int> dijkstra(int s, vector<vector<Edge>> g) {
  vector<int> dist(g.size(), INF);
  dist[s] = 0;

  priority_queue<P, vector<P>, greater<P>> q;
  q.emplace(0, s); // [現在位置のコスト, 位置位置]

  while (!q.empty()) {
    P p = q.top(); q.pop();
    auto d = p.first, v = p.second;
    if (dist[v] < d) continue;

    for (Edge e: g[v]) {
      if (dist[v]+e.cost < dist[e.to]) {
        dist[e.to] = dist[v] + e.cost;
        q.emplace(dist[e.to], e.to);
      }
    }
  }

  return dist;
}

void solve() {
  vector<vector<Edge>> g(n);
  REP(i,m) {
    Edge e = { b[i], c[i] };
    g[a[i]].emplace_back(e);
  }

  REP(i,n) {
    vector<int> d = dijkstra(i, g);

    int ans = INF;
    REP(j,n) {
      for(Edge e: g[j]) {
        if (e.to == i) ans = min(ans, d[j]+e.cost);
      }
    }

    cout << (ans == INF ? -1 : ans) << endl;
  }
}

int main() {
  cin >> n >> m;
  a.resize(m); b.resize(m); c.resize(m);
  REP(i,m) {
    cin >> a[i] >> b[i] >> c[i];
    a[i]--; b[i]--;
  }

  solve();
  return 0;
}
#include <bits/stdc++.h>
using namespace std;
using ll         = long long;
constexpr ll MOD = 1000000007;
#define REP(i, n) for (ll i = 0; i < (n); i++)
#define REP2(i, x, n) for (ll i = x; i < (n); i++)
#define PR(x) cout << (x) << "\n"
#define PS(x) cout << (x) << " "
#define PRYES(x) PR((x) ? "Yes" : "No")
const long long INF          = numeric_limits<long long>::max();
const long long DP_INF       = 1 << 29;
template <class T> using arr = vector<vector<T>>;
using vint                   = vector<int>;
using vll                    = vector<ll>;
// SourceTest用出力マクロ
#ifdef SOURCE_TEST
#define SPR(x) PR(x)
#define SPS(x) PS(x)
#define STRACE(var) cout << #var << "=" << var << endl;
#define SMAPTRACE(var)  \
    cout << #var << "=" \
         << "{" << var.first << "," << var.second << "}" << endl;
#else
#define SPR(x) \
    {}
#define SPS(x) \
    {}
#define STRACE(var) \
    {}
#define SMAPTRACE(var) \
    {}
#endif
template <class T> void dump(const vector<T>& vec) {
#ifdef SOURCE_TEST
    for (ll i = 0; i < vec.size(); ++i) {
        cout << vec[i] << ",";
    }
    cout << endl;
#endif
}
struct Item {
    ll to;
    ll minutes;

    friend ostream& operator<<(ostream& os, const Item& pos) {
#ifdef SOURCE_TEST
        os << "{" << pos.to << "," << pos.minutes << "}";
#endif
        return os;
    }
};

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

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

    vector<vector<Item>> routes(N);

    for (ll i = 0; i < M; ++i) {
        ll a, b, c;
        cin >> a >> b >> c;
        a--;
        b--;
        routes[a].push_back(Item{b, c});
    }

    for (const auto& v : routes) {
        dump(v);
    }

    for (ll n = 0; n < N; ++n) {
        priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> que;
        vll dist(N, INF);
        dist[n] = 0;
        que.push({dist[n], n});
        ll ans = INF;
        while (!que.empty()) {
            ll index = que.top().second;
            ll d     = que.top().first;
            que.pop();

            if (d > dist[index]) continue;
            STRACE(index);

            for (const auto& route : routes[index]) {
                if (chmin(dist[route.to], dist[index] + route.minutes)) {
                    que.push({dist[route.to], route.to});
                }
                if (route.to == n) {
                    chmin(ans, dist[index] + route.minutes);
                }
            }
            STRACE(ans);
            dump(dist);
        }

        if (ans == INF) {
            PR(-1);
        } else {
            PR(ans);
        }
    }

    return 0;
}