#include <bits/stdc++.h>
#define f first
#define s second
#define fore(i,a,b) for(int i = (a), ThxMK = (b); i < ThxMK; ++i)
#define pb push_back
#define all(s) begin(s), end(s)
#define _ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define sz(s) int(s.size())
#define ENDL '\n'
#define vv(type, name, h, ...) vector<vector<type>> name(h, vector<type>(__VA_ARGS__))
#define vvv(type, name, h, w, ...) vector<vector<vector<type>>> name(h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))
using namespace std;
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
typedef long long lli;
typedef pair<int,int> ii;
typedef vector<int> vi;
#define deb(x) cout << #x": " << (x) << endl;

lli gcd(lli a, lli b){return (b?gcd(b,a%b):a);}
lli lcm(lli a, lli b){ if(!a || !b) return 0; return a * b / gcd(a, b); }
int popcount(lli x) { return __builtin_popcountll(x); }

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int rnd(int n){return uniform_int_distribution<int>(0, n-1)(rng);}

lli poww(lli a, lli b){
	lli res =1;
	while(b){ if(b&1) res = res * a; a = a*a; b/=2; }
	return res;
}

vvc<int> graph(int n, int m, bool dir=1){
	vv(int,v,n+1,0);
	fore(i,0,m){
		int a,b; cin>>a>>b;
		v[a].pb(b);
		if(dir)v[b].pb(a);
	}
	return v;
}
template <typename T> static constexpr T inf = numeric_limits<T>::max() / 2;
// ---- コーディングはここから！ ('-')7


void solve(){
	int n,m; cin>>n>>m;
	vv(int,v,n,n,inf<int>);
	fore(i,0,m){
		int a,b,c; cin>>a>>b>>c;a--,b--;
		v[a][b]=min(v[a][b],c);
	}
	vv(ii,g,n+1);
	fore(i,0,n)fore(j,0,n)if(v[i][j]!=inf<int>)g[i].pb({j,v[i][j]});

	auto dij=[&](int a){
		using pp  = pair<int,lli>;
		priority_queue<pp>q;
		q.push({0,n});
		g[n]=g[a];
		vc<lli>dp(n+1,inf<lli>);
		dp[n]=0;
		while(!q.empty()){
			auto p=q.top(); q.pop();
			auto [y,x]=p;
			y*=-1;
			if(y!=dp[x])continue;
			if(x==a)return y;
			for(auto [i,j]:g[x])if(dp[i]>y+j){
				dp[i]=y+j;
				q.push({-dp[i],i});
			}
		}
		return -1;
	};
	fore(i,0,n)cout<<dij(i)<<ENDL;


}

int main(){_
	//int t; cin>>t; while(t--)
	solve();
}

//BISMILLAHIR RAHMANIR RAHIM
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define mem(a, b) (memset(a, b, sizeof(a)))
#define pb push_back
#define mk make_pair
#define ff first
#define ss second
#define PI acos(-1)
#define INF 2147483647
#define MOD 1000000007
#define MAX 2005
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<ii, int> pii;
typedef vector<ii> vii;
typedef priority_queue<int,vector<int>,greater<int> > PQ;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int setBit(int mask, int pos){return mask = mask | (1<<pos);}
bool checkBit(int mask, int pos){return (bool)(mask & (1<<pos));}

vector<pair<int, int> > adj[MAX];
ll dist[MAX][MAX];
int n;

void dijkstra(int src) {
	priority_queue<ii> q;

	q.push(mk(-0, src));
	dist[src][src] = 0;

	while (!q.empty()) {
		ii x = q.top();
		q.pop();
		int cur = x.ss;

		int sz = adj[cur].size();

		for (int i = 0; i < sz; i++) {
            if (dist[src][adj[cur][i].ff] > dist[src][cur] + adj[cur][i].ss) {
                dist[src][adj[cur][i].ff] = dist[src][cur] + adj[cur][i].ss;
                q.push(mk(-dist[src][adj[cur][i].ff], adj[cur][i].ff));
            }
		}
	}
}

int main() {
	int m;

	scanf("%d %d", &n, &m);
	vector<ll> ans(n + 1, INF);
	for(int i = 0; i <= n; i++) {
        for(int j = 0; j <= n; j++) {
            dist[i][j] = 1e12;
        }
	}

	map<ii, int> mp;
	for (int i = 0; i < m; i++) {
		int x, y, w;
		scanf("%d %d %d", &x, &y, &w);
		if(x == y) {
            ans[x] = min(ans[x], (ll) w);
		}
		else {
            if(mp.count(mk(x, y))) {
                mp[mk(x, y)] = min(mp[mk(x, y)], w);
            }
            else{
                mp[mk(x,y)] = w;
            }
		}
	}

	for(map<ii, int> :: iterator it = mp.begin(); it != mp.end(); it++) {
        adj[it->ff.ff].pb(mk(it->ff.ss, it->ss));
	}
	for(int i = 1; i <= n; i++) {
        dijkstra(i);
	}

	for(int j = 1; j <= n; j++) {
        for(int i = 1; i <= n; i++) {
            if(i != j) {
                ans[i] = min(ans[i], dist[i][j] + dist[j][i]);
            }
        }
	}

	for(int i = 1; i <= n; i++) {
        if(ans[i] == INF)
            printf("-1\n");
        else
            printf("%d\n", ans[i]);
	}

	return 0;
}

