#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int NR=2e3+5;
int n,m,dis[NR];
bool vis[NR];
struct node{
	int v,w;
};
vector<node>g[NR];
void SPFA (){
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	queue<int>q;
	q.push(1);
	dis[1]=0;
	vis[1]=1;
	while (!q.empty()){
		int tmp=q.front();q.pop();
		vis[tmp]=0;
		for (int i=0;i<g[tmp].size();++i){
			if (dis[g[tmp][i].v]>dis[tmp]+g[tmp][i].w){
				dis[g[tmp][i].v]=dis[tmp]+g[tmp][i].w;
				if (!vis[g[tmp][i].v]){
					q.push(g[tmp][i].v);
					vis[g[tmp][i].v]=1;
				}
			}
		}
	}
}
signed main (){
	cin>>n>>m;
	while (m--){
		int u,v,w;
		cin>>u>>v>>w;
		g[u].push_back({v,w});
	}
	SPFA();
	for (int i=1;i<=n;++i){
		if (dis[i]>=1e9) cout<<-1<<' ';
		else cout<<dis[i]<<' ';
	}
	return 0;
}