#include <fstream>
#include <queue>
#include <algorithm>
using namespace std;

#define maxn 50001
int inf=1<<30;

typedef struct graf{
	int nod,cost;};

queue <graf> q[maxn];
int d[maxn],heap[maxn],n,nh,m,pos[maxn];

void sw(int a,int b){
	swap(heap[a],heap[b]);
	pos[heap[a]]=a;
	pos[heap[b]]=b;}

void push(int k){
	while(k/2&&d[heap[k]]<d[heap[k/2]]){
		sw(k,k/2);
		k=k/2;}}

void sift(int k){
	int son;
	do{
		son=0;
		if(k*2<=nh)
			son=k*2;
		if(k*2+1<=nh&&d[heap[k*2]]>d[heap[k*2+1]])
			son=k*2+1;
		if(d[heap[son]]>d[heap[k]])
			son=0;
		if(son){
			sw(k,son);
			k=son;}}
	while(son);}

void pop(int k){
	sw(k,nh);
	nh--;
	push(k);
	sift(k);}

void dijkstra(int k){
	int nod,cost;
	pop(pos[k]);
	while(!q[k].empty()){
		nod=q[k].front().nod;
		cost=q[k].front().cost;
		if(d[k]+cost<d[nod]){
			d[nod]=d[k]+cost;
			push(pos[nod]);
			sift(pos[nod]);}
		q[k].pop();}
	if(nh)
		dijkstra(heap[1]);}


int main(){
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	f>>n>>m;
	int i,a,b,c;
	graf gr;
	for(i=1;i<=m;i++){
		f>>a>>b>>c;
		gr.nod=b;
		gr.cost=c;
		q[a].push(gr);}
	for(i=2;i<=n;i++)
		d[i]=inf;
    d[1]=0;
	for(i=1;i<=n;i++){
		nh++;
		heap[nh]=i;
		pos[i]=nh;
		push(nh);}
	dijkstra(1);
	for(i=2;i<=n;i++)
		if(d[i]==inf)
			g<<0<<" ";
		else g<<d[i]<<" ";
	f.close();
	g.close();
	return 0;}