/* Sat-Chitta-Ananda */

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define inf (int)1e9
#define f first
#define s second

int readInt() { int x; cin >> x; return x; }
char readChar() { char x; cin >> x; return x; }
int readDouble() { double x; cin >> x; return x; }
string readStr() { string x; cin >> x; return x; }

int Dijkstra(const vector<vector<pair<int,int>>> &g, const int &n, int sv) {
	vector<int> d(n, inf);
	d[sv] = 0;

	int ans = inf;

	priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> Queue;
	Queue.push({d[sv], sv});

	while(!Queue.empty()) {
		int node = Queue.top().s;
		int weight = Queue.top().f;
		Queue.pop();

		if(weight > d[node]) continue;

		for(auto itr : g[node]) {
			int distance = itr.f;
			int neighbor = itr.s;
			// itself
			if(neighbor == sv) {
				ans = min(ans, d[node] + distance);
			}
			else {
				if(d[neighbor] > d[node] + distance) {
					d[neighbor] = d[node] + distance;
					Queue.push({d[neighbor], neighbor});
				}
			}
		}
	}

	if(ans >= inf) ans = -1;
	return ans;
}

int32_t main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	int n = readInt();
	int m = readInt();

	vector<vector<pair<int,int>>> g(n);
	for(int i = 0 ; i < m ; ++i) {
		int a = readInt();
		int b = readInt();
		int c = readInt();
		g[a-1].push_back({c, b-1});
	}

	for(int i = 0 ; i < n ; ++i) {
		cout << Dijkstra(g, n, i) << '\n';
	}

	return 0;
}
#include <bits/stdc++.h>
//#include <atcoder/modint>
//#include <atcoder/math>
//#include <boost/multiprecision/cpp_int.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3")
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPP(i, n) for(int i = 1; i <= n; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define EPS (1e-9)
#define INF (1e17)
#define PI (acos(-1))
//const double PI = acos(-1);
//const double EPS = 1e-15;
//long long INF=(long long)1E17;
#define i_7 (long long)(1e9+7)
//#define i_7 998'244'353
long mod(long a){
    long long c = a % i_7;
    if(c >= 0) return c;
    return c + i_7;
}
long long po(long a, long b){
    if(b == 0) return 1;
    
    long long z = po(a , b / 2);
    z = mod(z * z);
    if(b % 2 != 0) z = mod(a * z);
    return z;
}

bool prime_(int n){
    if(n == 1){
        return false;
    }else if(n == 2){
        return true;
    }else{
        for(int i = 2; i <= std::sqrt(n); i++) if(n % i == 0) return false;
        return true;
    }
}

long long gcd_(long long a, long long b){
    if(a < b) std::swap(a,b);
    if(a % b == 0) return b;
    else return gcd_(b, a % b);
}

long long lcm_(long long x, long long y){
    return (x / gcd_(x,y)) * y;
}

using namespace std;
//using namespace atcoder;
//using mint = modint1000000007;
//using mint = modint998244353;
//using namespace boost::multiprecision;
//using namespace __gnu_pbds;

typedef pair<int, int> P;
unordered_map<int, int> G[2010];

int main(){
    //using namespace std;
    
    int n, m;
    cin>>n>>m;
    int a[m], b[m], c[m];
    REP(i, m){
        cin>>a[i]>>b[i]>>c[i];
        a[i]--; b[i]--;
    }
    
    REP(i, m){
        if(G[a[i]].find(b[i]) == G[a[i]].end()){
            G[a[i]][b[i]] = c[i];
            continue;
        }
        G[a[i]][b[i]] = min(G[a[i]][b[i]], c[i]);
    }
    
    vector<int> ans(n, -1);
    REP(st, n){
        //cout << "st: " << st << endl;
        vector<int> dist(n, -1);
        dist[st] = 0;
        priority_queue<P, vector<P>, greater<P>> pq;
        pq.emplace(0, st);
        while(!pq.empty()){
            int now = pq.top().second;
            int d = pq.top().first;
            //cout << "now: " << now << "d: " << d << endl;
            pq.pop();
            if(dist[now] > 0 && dist[now] < d) continue;
            if(now == st && d > 0) continue;
            //if(now == st && d > 0) break;
            for(auto& [nxt, cost]: G[now]){
                if(nxt != st && nxt == now) continue;
                if(dist[nxt] > 0 && dist[nxt] <= d + cost) continue;
                dist[nxt] = d + cost;
                pq.emplace(dist[nxt], nxt);
            }
        }
        ans[st] = dist[st] == 0 ? -1 : dist[st];
    }
    REP(i, n) cout << ans[i] << endl;
    return 0;
}