// FIRST THINK THEN CODE.

#include<iostream>
#include <bits/stdc++.h>

using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define cld complex<ld>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vld vector<ld>
#define vvld vector<vector<ld>>
#define vpll vector<pll>
#define vcld vector<cld>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define eb emplace_back
#define PI acos(-1)
#define endl "\n"
#define fix(f,n) fixed<<setprecision(n)<<f
#define all(x) x.begin(),x.end()
#define rev(p) reverse(p.begin(),p.end());
#define mset(a,val) memset(a,val,sizeof(a));
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define popcount(x) __builtin_popcountll(x)
#define sz(x) ((ll)x.size())
#define FOR(i,a,b)  for(ll i=a;i<=b;i++)
#define FORR(i,a,b)  for(ll i=a;i>=b;i--)
const ll M = 1000000007;
const ll MM = 998244353;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define ordered_set tree<pll, null_type,less<>, rb_tree_tag,tree_order_statistics_node_update>

ll begtime = clock();
#define end_routine() cerr << "\n\nTime elapsed: " << (clock() - begtime)*1000/CLOCKS_PER_SEC << " ms\n\n";

template<typename T, typename F>
void chmax( T &a, F b) {
	if (b > a)a = b;
}

template<typename T, typename F>
void chmin( T &a, F b) {
	if (b < a)a = b;
}

const ll N = 2e5 + 5;

vpll arr[N];

vl self(N, 1e9);

ll dji(ll node) {
	vl vis(2005);
	vis[node] = 1;
	vl dis(2005, 1e18);
	set<pll>s;
	dis[node] = 0;
	ll flag = 0;
	s.insert({dis[node], node});
	while (sz(s)) {
		auto f = *s.begin();
		auto n1 = f.ss;
		s.erase(s.begin());
		for (auto to : arr[n1]) {
			ll child = to.ff, d = to.ss;
			if (child == node) {
				if (!dis[node]) {
					dis[node] = 1e9;
				}
			}

			if (dis[child] > dis[n1] + d) {
				s.erase({dis[child], child});
				dis[child] = dis[n1] + d;
				s.insert({dis[child], child});
			}
		}
	}
	if (!dis[node])dis[node] = 1e9;
	chmin(dis[node], self[node]);
	if (dis[node] == 1e9)dis[node] = -1;
	return dis[node];
}


void OJ() {


#ifndef ONLINE_JUDGE

	freopen("input1.txt", "r", stdin);
	freopen("output1.txt", "w", stdout);

#endif

}

int main() {

	IOS;

	OJ();


	ll n; cin >> n;

	ll m; cin >> m;


	for (ll i = 1; i <= m; i++) {
		ll x, y, d;
		cin >> x >> y >> d;
		if (x == y) {
			chmin(self[x], d);
		} else {
			arr[x].pb({y, d});
		}
	}


	for (ll i = 1; i <= n; i++) {
		cout << dji(i) << endl;
	}



	return 0;


}


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

using namespace std;

typedef long long ll;

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

// dijkstra 蟻本
struct edge {ll to, cost;};
typedef pair<ll, ll> P; // firstはsからの最短距離, secondは頂点の番号
const ll INF = 1e17;
const int max_n = 101010;

int n;
vector<edge> g[max_n];

void dijkstra(ll s, vector<ll> &d){

	priority_queue<P,vector<P>,greater<P> > que;
	que.push(P(0, s));

	while(!que.empty()){
		P p = que.top();
		que.pop();

		ll v = p.second;
		if(d[v] < p.first) continue; //後から最短パスが見つかった場合、先にqueに入っているものはここではじかれる

		for(ll i = 0; i < g[v].size(); i++){
			edge e = g[v][i];
			if(d[e.to] > p.first + e.cost){
				d[e.to] = p.first + e.cost;
				que.push(P(d[e.to], e.to));
			}
		}
	}
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);

	int n, m;
	cin >> n >> m;

	rep(i, m){
		int a, b;
		ll c;
		cin >> a >> b >> c;
		a--; b--;
		g[a].push_back({b, c});
	}

	vector<vector<ll>> dist(n, vector<ll>(n, INF));
	rep(i, n) dijkstra(i, dist[i]);
	rep(i, n) cout << (dist[i][i] == INF ? -1 : dist[i][i]) << endl;
}
