#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;

const int NMAX=5e4;
struct muchie{
	int id,cost;
};
vector<muchie> g[NMAX+1];
uint32_t d[NMAX+1];
struct comp{
	inline bool operator()(const int& a, const int& b){
		return d[a]>d[b];
	}
};
bool inq[NMAX+1];

int main(){
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	int n,m;
	cin>>n>>m;
	while(m--){
		int a,b,c;
		cin>>a>>b>>c;
		g[a].push_back({b,c});
	}
	memset(d+2,-1,(n-1)*sizeof(*d));
	priority_queue<int,vector<int>,comp> pq;
	pq.push(1);
	inq[1]=1;
	while(!pq.empty()){
		int nod=pq.top();
		pq.pop();
		inq[nod]=0;
		for(auto i:g[nod]){
			if(d[i.id]>d[nod]+i.cost){
				d[i.id]=d[nod]+i.cost;
				if(!inq[i.id]){
					pq.push(i.id);
					inq[i.id]=1;
				}
			}
		}
	}
	for(int i=2;i<=n;++i){
		if(d[i]!=uint32_t(-1)){
			cout<<d[i]<<' ';
		}else{
			cout<<"0 ";
		}
	}
}