#include<bits/stdc++.h>
using namespace std;
typedef long long ll;//宏定义  把ll当作long long使用 
const ll N=1e5+100;
ll n,m,ans,dist[N],mk[N];
vector<pair<ll,ll>> v[N];
priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> q;//小优先队列 
void Dijkstra(){
	for(int i=1;i<=n;i++) dist[i]=1e9;
	dist[1]=0;
	q.push({0,1});//先存距离再存点
	while(q.size()){
		pair<ll,ll> p=q.top();q.pop();
		ll x=p.second;//当前的点
		if(mk[x]==1) continue; 
		mk[x]=1;
		//松弛操作
		for(int i=0;i<v[x].size();i++){
			ll xx=v[x][i].first;//出边点
			ll qz=v[x][i].second;//边上的权
			if(dist[xx]>dist[x]+qz) dist[xx]=dist[x]+qz,q.push({dist[xx],xx}); 
		} 
	} 
}
int main(){
	cin>>n>>m;
	while(m--){
		ll x,y,z;
		cin>>x>>y>>z;
		v[x].push_back({y,z});
	} 
	Dijkstra();
	for(int i=1;i<=n;i++) cout<<dist[i]<<" ";
	if(dist[n]==1e9) dist[n]=-1;
	cout<<dist[n];
	return 0;
}