#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <bitset>
using namespace std;
#define MAXN 50002

struct muchie {
	int urm;
	int cost;
};

typedef vector<muchie> nod;
FILE *fin, *fout;

int n,m,a,b,c,i,noda,cost,facute;
vector<muchie> graf[MAXN];
vector<muchie> heap;
bitset<MAXN> done;
int minim[MAXN];
muchie m_aux;

inline bool comp(muchie a, muchie b) {
	return (a.cost>b.cost);
}

void citire() {
	fscanf(fin,"%d %d\n",&n,&m);
	for(i=1;i<=m;++i) {
		fscanf(fin,"%d %d %d\n",&a,&m_aux.urm,&m_aux.cost);
		graf[a].push_back(m_aux);		
	}
	for(i=1;i<=n;++i) minim[i]=268435456;
	facute=n;
}

void scriere() {
	for(i=2;i<n;++i) {
		fprintf(fout,"%d ",minim[i]);
	}
	fprintf(fout,"%d",minim[n]);
}

void dijkstra() {	
	while (!heap.empty()) {
		noda=heap[0].urm;
		cost=heap[0].cost;		
		pop_heap(heap.begin(),heap.end(),comp);
		heap.pop_back();
		if (!done[noda]) {
			minim[noda]=cost;
			done[noda]=1;
			facute--;
			if (facute==0) return;
			for(i=0;i<graf[noda].size();++i){
				if ( (!done[graf[noda][i].urm])&&(cost+graf[noda][i].cost<minim[graf[noda][i].urm]) ) {
					m_aux.urm=graf[noda][i].urm;
					m_aux.cost=graf[noda][i].cost+cost;
					minim[graf[noda][i].urm]=m_aux.cost;
					heap.push_back(m_aux);
					push_heap(heap.begin(),heap.end(),comp);
				}
			}			
		}
	}
}



int main() {
	fin=fopen("dijkstra.in","r"); fout=fopen("dijkstra.out","w");
	citire();
	m_aux.urm=1;
	m_aux.cost=0;
	heap.push_back(m_aux);
	dijkstra();
	
	
	scriere();
	fclose(fin); 
	fclose(fout);
	return 0;	
}