/*                                                       
  /^--^\                                                 
  \____/                                                 
 /      \ _____  _ __  __ ____  _     ____   ____  _____ 
|        || ()_)| |\ \/ /| ===|| |__ / (__` / () \|_   _|
 \__  __/ |_|   |_|/_/\_\|____||____|\____)/__/\__\ |_|  
|^|^\ \^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|
| | |\ \| | | | | | | | | | | | | | | | | | | | | | | | |
#####/ /#################################################
| | |\/ | | | | | | | | | | | | | | | | | | | | | | | | |
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|*/
#pragma GCC optimize("O4,unroll-loops,no-stack-protector")
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<ll,ll>;
#define int ll
#define double long double

#define For(i,a,b)  for(int i=a;i<=b;i++)
#define Forr(i,a,b) for(int i=a;i>=b;i--)
#define Fors(i,a,b,s) for(int i=a;i<=b;i+=s)
#define F first
#define S second
#define L(id) (id*2+1)
#define R(id) (id*2+2)

#define eb emplace_back
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define mkp make_pair

#define MOD (ll)(998244353)
#define INF (1e17)
#define EPS (1e-6)

#ifdef LOCALMEOW
#define debug(...) do{\
	cerr << __PRETTY_FUNCTION__ << " - " << __LINE__ <<\
	" : ("#__VA_ARGS__ << ") = ";\
	_OUT(__VA_ARGS__);\
}while(0)
template<typename T> void _OUT(T x) { cerr << x << "\n"; }
template<typename T,typename...I>
void _OUT(T x,I ...tail) { cerr << x << ", "; _OUT(tail...); }
#else
#define debug(...)
#endif
inline void IOS(){ ios::sync_with_stdio(false); cin.tie(0); }

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int gcd(int a,int b) { return b==0?a:gcd(b,a%b); }
int lcm(int a,int b) { return a/gcd(a,b)*b; }
int fpow(int b,int p){
	int ans=1,now=b;
	while(p){
		if(p&1) ans=ans*now%MOD;
		p/=2; now=now*now%MOD;
	}
	return ans;
}
void minify(int &a,int b) { if(b<a) a=b; }
void maxify(int &a,int b) { if(b>a) a=b; }

vector<pii> adj[2020];
int dis[2020];

int dijk(int n){
	For(i,0,2019) dis[i]=INF;
	priority_queue<pii,vector<pii>,greater<pii>> pq;
	for(auto &i:adj[n])
		pq.emplace(i.S,i.F);
	while(!pq.empty()){
		auto p=pq.top(); pq.pop();
		if(p.S==n) return p.F;
		if(dis[p.S]!=INF) continue;
		dis[p.S]=p.F;
		for(auto &e:adj[p.S]){
			pq.emplace(e.S+p.F,e.F);
		}
	}
	return -1;
}

int32_t main(){
	IOS();
	//code...
	int n,m; cin>>n>>m;
	int a,b,c;
	For(i,0,m-1){
		cin>>a>>b>>c;
		adj[a].eb(b,c);
	}
	For(i,1,n) cout<<dijk(i)<<"\n";
	return 0;
}
#include<bits/stdc++.h>
using namespace std;

#define all(x) (x).begin(),(x).end()
#define pb push_back
#define pf push_front
#define sz(x) (int)(x).size()
#define lb lower_bound 
#define ub upper_bound 
#define mp make_pair
#define fi first
#define se second
#define setbits(x) __builtin_popcount(x)
#define zerobits(x) __builtin_ctz(x)
#define setbitsll(x) __builtin_popcountll(x)
#define zerobitsll(x) __builtin_ctzll(x)
#define ps(x,y) fixed<<setprecision(y)<<x

typedef vector<int> vi;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
typedef map<int,int> mii;

const int MOD = 1e9+7;
const ld PI = acos((ld)-1);
const int maxN = 2001;

vector<pii> adj[maxN];
vi res(maxN,MOD);
vector<vector<int>>dist(maxN,vector<int>(maxN,MOD));

void dijkstra (int src) {
	dist[src][src] = 0;
	priority_queue<pii>pq;
	pq.push({0,src});
	while (!pq.empty()) {
		pii p = pq.top();
		pq.pop();
		int d = -p.fi;
		int v = p.se;
		if (d > dist[src][v]) {
			continue;
		}
		for (pii edge : adj[v]) {
			int to = edge.fi;
			int w = edge.se;
			if (dist[src][to] > dist[src][v]+w) {
				dist[src][to] = dist[src][v]+w;
				pq.push({-dist[src][to],to});
			}
		}
	}
	
}

void solve () {
	int n,m;
	cin >> n >> m;
	for (int i = 0;i < m;++i) {
		int u,v,w;
		cin >> u >> v >> w;
		if (u == v) {
			res[u] = min(res[u],w);
			continue;
		}
		adj[u].pb({v,w});
	}
	for (int i = 1;i <= n;++i) {
		dijkstra(i);
	}
	for (int i = 1;i <= n;++i) {
		for (pii edge : adj[i]) {
			int to = edge.fi;
			int w = edge.se;
			res[i] = min(res[i],dist[to][i]+w);
		}
	}
	for (int i = 1;i <= n;++i) {
		if (res[i] == MOD) {
			cout << -1 << "\n";
		} else {
			cout << res[i] << "\n";
		}
	}
}

int main () {

#ifndef ONLINE_JUDGE
	freopen("input1.txt","r",stdin);
	freopen("output1.txt","w",stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	solve();
	return 0;
}

