#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define rep(i, n) for (int i = 0, i##_len = (int)(n); i < i##_len; i++)
#define reps(i, n) for (int i = 1, i##_len = (int)(n); i <= i##_len; i++)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define repi(i, x) \
	for (auto i = (x).begin(), i##_fin = (x).end(); i != i##_fin; i++)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef pair<int, int> Pi;
typedef vector<Pi> VPi;
typedef vector<long long> V;
typedef vector<V> VV;
typedef pair<long long, long long> P;
typedef vector<P> VP;
template <class T>
inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return 1;
	}
	return 0;
}
template <class T>
inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return 1;
	}
	return 0;
}
template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
	os << "(" << p.first << " " << p.second << ")";
	return os;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	rep(i, v.size()) {
		if (i) os << " ";
		os << v[i];
	}
	return os;
}
template <class T, class U>
istream& operator>>(istream& is, pair<T, U>& p) {
	is >> p.first >> p.second;
	return is;
}
template <class T>
istream& operator>>(istream& is, vector<T>& v) {
	rep(i, v.size()) { is >> v[i]; }
	return is;
}
const long long INFLL = 1LL << 60;
const int INF         = 1 << 30;
const double PI       = acos(-1);
#ifdef LOCAL
#define dbg(x) cerr << #x << ": " << (x) << '\n'
#define say(x) cerr << (x) << '\n'
#else
#define dbg(x)
#define say(x)
#endif
//ダイクストラ法:スタートから任意の地点での最短距離、最短パスを求める
//計算量:(頂点+辺)log(頂点)
//始点,終点,隣接リスト(pathlist[edge.A]=(edgeB,legth))-->距離(notfound:INFLL),previous(notfound:INF);
vector<pair<long long, int>> Dikstra(
    int start, vector<vector<pair<int, long long>>>& pathlist) {
	int edge = pathlist.size();
	pair<long long, int> cerching;
	priority_queue<pair<long long, int>, vector<pair<long long, int>>,
	               greater<pair<long long, int>>>
	    q;  // start to distance,[ditance ,islandNo.]
	vector<pair<long long, int>> D(
	    edge, mp(INFLL, INF));  // distance (ans), preious path
	vector<bool> had(edge, false);
	D[start] = mp(0, -1);  // distance ,Previous egdg
	q.emplace(0LL, start);
	while (!q.empty()) {
		cerching = q.top();
		q.pop();
		if (had[cerching.second] == false) {
			had[cerching.second] = true;
			for (auto i = pathlist[cerching.second].begin();
			     i != pathlist[cerching.second].end(); i++) {
				if (had[i->first] == false) {
					if (chmin(D[i->first].F, (cerching.first) + (i->second))) {
						D[i->first].S = cerching.second;
					}
					q.emplace(D[i->first].F, i->first);
				}
			}
		}
	}

	return D;
}
string solve(bool a) { return ((a) ? "Yes" : "No"); }
int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	vector<vector<pair<int, long long>>> path(n);
	VV dis(n, V(n, INFLL));
	int a, b, c;
	rep(i, m) {
		cin >> a >> b >> c;
		path[a - 1].emplace_back(b - 1, c);
		chmin(dis[a - 1][b - 1], (ll)c);
	}
	vector<pair<long long, int>> res;
	rep(i, n) {
		res = Dikstra(i, path);
		rep(j, n) {
			if (res[j].F == 0) continue;

			chmin(dis[i][j], res[j].F);
		}
	}
	rep(i, n) {
		ll ans = INFLL;
		chmin(ans, dis[i][i]);
		rep(j, n) { chmin(ans, dis[i][j] + dis[j][i]); }
		if (ans == INFLL) {
			cout << -1 << endl;
		} else {
			cout << ans << endl;
		}
	}
}

#include <bits/stdc++.h>
 
typedef long long int ll;
typedef long double ld;
typedef unsigned long long int ull;
typedef long int li;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 
#define test ll t; cin >> t; while(t--)
const long long int dx[4] = {0, 0, -1, 1}, dy[4] = {1, -1, 0, 0}; 
const long long int cons = 100005, ncr_cons = 100005;
const long long int MOD = 1000000007; // const long long int MOD = 998244353; 
const long long int const_INT_MAX = 1000000000000000000, const_INT_MIN = -1 * 1000000000000000000;
using namespace std;
bool sortinrev(const pair<ll,ll> &a, const pair<ll,ll> &b){return (a.first > b.first);}
bool sortbysec(const pair<ll,ll> &a, const pair<ll,ll> &b){return (a.second < b.second);}
bool sortbysecinrev(const pair<ll,ll> &a, const pair<ll,ll> &b){return (a.second > b.second);}
ll gcd(ll x, ll y){return (ll)(__gcd(x, y));}   
ll lcm(ll x, ll y){return (ll)((x * y) / gcd(x, y));}
ll mod_expo(ll x, ll y, ll p){  
    if((x + p) % p == 0) return 0; 
    ll res = 1; x = (x + p) % p; 
    while (y > 0){   
        if(y & 1) res = (res*x + p) % p; 
        y = y>>1; x = (x*x + p) % p;  
    }  
    return res;    
}
void usaco(string str = ""){    
    fastio; 
    if(str.size()){
        freopen((str + ".in").c_str(), "r", stdin); 
        freopen((str + ".out").c_str(), "w", stdout);
    }   
}  
vector<pair<ll, ll>> adj[cons];
vector<ll> par, dist; 
void dijkstra(ll n, ll source){
	par.assign(n + 1, -1); dist.assign(n + 1, const_INT_MAX); 
	priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> p; 
	p.push(make_pair(0, source)); dist[source] = 0; 
	while(p.size() > 0){
		pair<ll, ll> v = p.top(); p.pop();  
		if(dist[v.second] < v.first) continue; // already initialised
		else {
			for(auto u : adj[v.second]){
				if(dist[v.second] + u.second < dist[u.first]){
					dist[u.first] = dist[v.second] + u.second; par[u.first] = v.second; 
					p.push(make_pair(dist[u.first], u.first)); 
				}
			}
		}
	}
}
int main(){ 
    usaco();
    ll n, m; cin >> n >> m; 
    vector<ll> fin_ans(n, const_INT_MAX); 
    for(ll i=0;i<m;i++){
    	ll a, b, c; cin >> a >> b >> c; a--; b--; 
    	if(!(a - b)) fin_ans[a] = min(fin_ans[a], c); 
    	else {
    		adj[a].push_back(make_pair(b, c)); 
    	} 
    }
    for(ll i=0;i<n;i++){
    	for(auto u : adj[i]){
    		dijkstra(n, (ll)(u.first)); 
    		fin_ans[i] = min(fin_ans[i], u.second + dist[i]); 
    	}
    }
    for(ll i=0;i<n;i++){
    	if(!(fin_ans[i] - const_INT_MAX)) cout << -1 << "\n";
    	else cout << fin_ans[i] << "\n";
    }
    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n"; 
}

