#include <fstream>
#include <vector>
#define NMAx 50100
#define inf (1<<28)
#define left(i) (2*i)
#define right(i) (2*i+1)
#define father(i) (i/2)
#define cmp(a,b) (dist[heap[a]]<dist[heap[b]])
using namespace std;
vector <unsigned short> G[NMAx],Cost[NMAx];
int n,vf=1,heap[NMAx],dist[NMAx],loc[NMAx];

void up(int nod) {
	
	while(nod>1&&cmp(nod,father(nod))) {
		swap(heap[nod],heap[father(nod)]);
		swap(loc[nod],loc[father(nod)]);
		nod=father(nod);
		}
	
}
void down(int nod) {
	
	int son;
	do {
		son=0;
		if(left(nod)<=vf) {
			son=left(nod);
			if(right(nod)<=vf&&cmp(right(nod),left(nod)))
				son=right(son);
			if(cmp(nod,son))
				son=0;
			}
		if(son) {
			swap(heap[nod],heap[son]);
			swap(loc[nod],loc[son]);
			nod=son;
			}
	}while(son);
	
}
void dijkstra() {
	int nod,vecin,i;
	heap[1]=1;
	while(vf) {
		nod=heap[1];
		loc[nod]=-1;
		heap[1]=heap[vf--];
		loc[heap[1]]=1;
		down(1);
		for(i=0;i<G[nod].size();i++) {
			vecin=G[nod][i];
			if(!loc[vecin]) {
				heap[++vf]=vecin;
				loc[vecin]=vf;
				dist[vecin]=dist[nod]+Cost[nod][i];
				up(loc[vecin]);
				}
			else
			if(dist[vecin]>dist[nod]+Cost[nod][i]) {
				dist[vecin]=dist[nod]+Cost[nod][i];
				up(loc[vecin]);
				}
			}
		}
}
void citire() {
	
	int i,x,y,c,m;
	ifstream in("dijkstra.in");
	in>>n>>m;
	for(i=0;i<m;i++) {
		in>>x>>y>>c;
		G[x].push_back(y);
		Cost[x].push_back(c);
		}
	in.close();
	
}
void afis() {

	int i;
	ofstream out("dijkstra.out");
	for(i=2;i<=n;i++)
	if(dist[i]==inf)
		out<<"0 ";
	else
		out<<dist[i]<<' ';
	out<<'\n';
	out.close();
	
}
int main() {
	
	citire();
	dijkstra();
	afis();

	return 0;
	
}