#include <bits/stdc++.h>
using namespace std;
#define INF 1<<30
int adj[2001][2001];
set<int> nb[20001];
int n;
int walk(int root) {
	vector<int> d(n+1, INF);
	set<pair<int, int> > q;
	for(set<int>::iterator i = nb[root].begin(); i!=nb[root].end(); i++){
		q.insert(make_pair(adj[root][*i], *i));
		d[*i]=adj[root][*i];
	}
	while (!q.empty()) {
		int v = q.begin()->second;
		q.erase(q.begin());
        for (set<int>::iterator is=nb[v].begin(); is!=nb[v].end(); is++) {
            int to = *is;
            int len = adj[v][*is];
			if (d[v] + len < d[to]) {
                q.erase(make_pair(d[to], to));
                d[to] = d[v] + len;
                q.insert(make_pair(d[to], to));
            }
        }
	}
	if(d[root]==INF) return -1;
	return d[root];
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int m;
	cin >> n >> m;
	for(int i = 1; i<=n; i++) for(int j = 1; j<=n; j++) adj[i][j] = INF;
	for(int i = 0; i<m; i++){
		int a, b, c;
		cin >> a >> b >> c;
		adj[a][b] = min(adj[a][b], c);
		nb[a].insert(b);
	}
	for(int i = 1; i<=n; i++){
		cout << walk(i) << '\n';
	}
	return 0;
}

#include <bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
const int MOD = 1000000007;
const int INF = 10000000000000;
using Graph = vector<vector<int>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

void dijkstra(vector<vector<pair<int, int>>> &G, int s,
              vector<int> &dist) {  //スタート地点を指定
    //コスト、向かう頂点でpair(コストが小さい順に並ぶ)
    priority_queue<pair<int, int>, vector<pair<int, int>>,
                   greater<pair<int, int>>>
        que;
    que.push(make_pair(0, s));
    while (!que.empty()) {
        pair<int, int> P = que.top();
        que.pop();
        int v = P.second;
        if (dist[v] < P.first)
            continue;
        dist[v] = P.first;
        for (auto &next : G.at(v)) {
            que.push({dist[v] + next.second, next.first});
        }
    }
}

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

    vector<vector<pair<int, int>>> G(N);
    vector<int> ans(N, INF);
    rep(i, M) {
        int A, B, C;
        cin >> A >> B >> C;
        A--;
        B--;
        if (A == B)
            ans[A] = min(ans[A], C);
        else
            G[A].emplace_back(make_pair(B, C));
    }

    rep(i, N) {
        for (auto nx : G[i]) {
            int cost = nx.second;
            int nv = nx.first;
            vector<int> dist(N, INF);
            dijkstra(G, nv, dist);
            ans[i] = min(dist[i] + cost, ans[i]);
        }
    }

    rep(i, N) {
        if (ans[i] == INF)
            cout << -1 << "\n";
        else
            cout << ans[i] << "\n";
    }
}
