#include<bits/stdc++.h>
using namespace std;
/*Shortest Path Code*/
int main(){
	cin>>n>>m;
	init();
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		add(u,v,w);
	}
	solve();
	for(int i=1;i<=n;i++)
		cout<<(dis[i]==inf?-1:dis[i])<<'\n';
	return 0;
}