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

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

typedef struct graf{
	int nod,cost;
	graf *next;};

graf *y[maxn];
int heap[maxn],n,nh,m,pos[maxn],viz[maxn],d[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--;
	if(k/2&&d[heap[k]]<d[heap[k/2]])
		push(k);
	else sift(k);}

void dijkstra(){
	int k,nod,cost;
	graf *q;
	d[1]=0;
	nh++;
	heap[1]=1;
	pos[1]=1;
	viz[1]=1;
	while(nh){
		k=heap[1];
		viz[k]=2;
		pop(1);
		q=new graf;
		q=y[k];
		while(q){
			nod=q->nod;
			cost=q->cost;
			if(viz[nod]<2&&d[k]+cost<d[nod]){
				d[nod]=d[k]+cost;
				if(viz[nod]==0){
					nh++;
					heap[nh]=nod;
					pos[nod]=nh;
					push(nh);}
				if(viz[nod]==1){
					if(pos[nod]/2&&heap[pos[nod]]<heap[pos[nod]/2])
						push(pos[nod]);
					else sift(pos[nod]);}}
			q=q->next;}}}

int main(){
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	f>>n>>m;
	int i,a,b,c;
	graf *q;
	for(i=1;i<=m;i++){
		f>>a>>b>>c;
		q=new graf;
		q->nod=b;
		q->cost=c;
		q->next=y[a];
		y[a]=q;}
	for(i=2;i<=n;i++)
		d[i]=inf;
	dijkstra();
	for(i=2;i<=n;i++){
		if(d[i]==inf)
			d[i]=0;
		g<<d[i]<<" ";}
	f.close();
	g.close();
	return 0;}