#include <stdio.h>
#include <vector>
using namespace std;
#define FI fopen("dijkstra.in","r")
#define FO fopen("dijkstra.out","w")

struct Legaturi {
	long dest;
	int cost;
};
struct Nod {
	long long dist;
	vector<Legaturi> legaturi;
} nod[50001];
long n,heap[50001],vec[50001],heapSize;

void citeste(FILE *f) {
	long i,m;
	long a,b;
	int c;
	fscanf(f,"%li%li",&n,&m);
	for(i=0;i<m;i++) {
		fscanf(f,"%li%li%i",&a,&b,&c);
		nod[a].legaturi.push_back((Legaturi) {b,c});
	}
	for(i=2;i<=n;i++)
		nod[i].dist=0x7fffffffffffffffll;
}

void heapBalance(long i) {
	long aux;
	while(nod[heap[i]].dist<nod[heap[i/2]].dist) {
		aux=heap[i];heap[i]=heap[i/2];heap[i/2]=aux;
		vec[heap[i]]=i;
		i/=2;
		vec[heap[i]]=i;
	}
	while((i*2<heapSize || i*2+1<heapSize) && (nod[heap[i*2]].dist<nod[heap[i]].dist || nod[heap[i*2+1]].dist<nod[heap[i]].dist))
		if(i*2+1<heapSize && nod[heap[i*2+1]].dist<nod[heap[i*2]].dist) {
			aux=heap[i];heap[i]=heap[i*2+1];heap[i*2+1]=aux;
			vec[heap[i]]=i;
			i=i*2+1;
			vec[heap[i]]=i;
		}
		else
			if(i*2<heapSize) {
				aux=heap[i];heap[i]=heap[i*2];heap[i*2]=aux;
				vec[heap[i]]=i;
				i*=2;
				vec[heap[i]]=i;
			}
}

void heapAdd(long val) {
	long i,aux;
	heap[heapSize]=val;
	heapSize++;
	i=heapSize-1;
	while(nod[heap[i]].dist<nod[heap[i/2]].dist && i>1) {
		aux=heap[i];heap[i]=heap[i/2];heap[i/2]=aux;
		vec[heap[i]]=i;
		i/=2;
		vec[heap[i]]=i;
	}
}

long heapRemove() {
	long i,aux,ret=heap[1];
	vec[heap[1]]=0;
	heapSize--;
	heap[1]=heap[heapSize];
	i=1;
	while((i*2<heapSize || i*2+1<heapSize) && (nod[heap[i*2]].dist<nod[heap[i]].dist || nod[heap[i*2+1]].dist<nod[heap[i]].dist))
		if(i*2+1<heapSize && nod[heap[i*2+1]].dist<nod[heap[i*2]].dist) {
			aux=heap[i];heap[i]=heap[i*2+1];heap[i*2+1]=aux;
			vec[heap[i]]=i;
			i=i*2+1;
			vec[heap[i]]=i;
		}
		else
			if(i*2<heapSize) {
				aux=heap[i];heap[i]=heap[i*2];heap[i*2]=aux;
				vec[heap[i]]=i;
				i*=2;
				vec[heap[i]]=i;
			}
	return ret;
}

void dijkstra() {
	long front,lim,i;
	heapAdd(1);
	while(heapSize>1) {
		front=heapRemove();
		lim=nod[front].legaturi.size();
		for(i=0;i<lim;i++)
			if(nod[front].dist+nod[front].legaturi[i].cost<nod[nod[front].legaturi[i].dest].dist) {
				nod[nod[front].legaturi[i].dest].dist=nod[front].dist+nod[front].legaturi[i].cost;
				if(vec[nod[front].legaturi[i].dest])
					heapBalance(nod[front].legaturi[i].dest);
				else
					heapAdd(nod[front].legaturi[i].dest);
			}
	}
}

void scrie(FILE *f) {
	long i;
	for(i=2;i<=n;i++)
		if(nod[i].dist<0x7fffffffffffffffll)
			fprintf(f,"%lli ",nod[i].dist);
		else
			fprintf(f,"0 ");
}

int main() {
	citeste(FI);
	heapSize=1;
	dijkstra();
	scrie(FO);
	return 0;
}