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

ifstream in ("dijkstra.in");
ofstream out ("dijkstra.out");

int n,m,cost[50002],heap[50003];
bool use[50002];
vector <pair <int, int> > a[50002];

void read () {
	in >> n >> m;
	for (int i = 1,x,y,z; i <= m; ++i) {
		in >> x>>y>>z;
		a[x].push_back(make_pair(y,z));
	}
}

void swap (int &a,int& b){
	int aux= a;
	a=b;b=aux;
}

void down (int nod) {
	int l = nod*2,r=nod*2+1,best=nod;
	if(l<=heap[0]&&cost[heap[l]]<cost[heap[nod]])best=l;
	if(r<=heap[0]&&cost[heap[r]]<cost[heap[best]])best=r;
	if(best!=nod){
		swap(heap[nod],heap[best]);
		down(best);
	}
}

void up(int nod){
	if (nod > 1 && cost[heap[nod]]<cost[heap[nod/2]]){
		swap(heap[nod],heap[nod/2]);
		up(nod/2);
	}
}

int pop () {
	swap (heap[heap[0]--],heap[1]);
	down(1);
	return heap[heap[0]+1];
}

void push (int x) {
	heap[++heap[0]] = x;
	up(heap[0]);
}

void dijkstra () {
	cost[1] = 0;
	for (int i = 2; i <= n; ++i) cost[i] = 2147483646;
	heap[++heap[0]] = 1;
	int x;
	while (heap[0]) {
		x = pop ();
		
		if (use[x]) {
			continue;
		}
		use[x] = true;
		
		for (size_t i = 0; i < a[x].size(); ++i) {
			if (cost[x] + a[x][i].second < cost[a[x][i].first]) {
				cost[a[x][i].first] = cost[x] + a[x][i].second;
				push (a[x][i].first);
			}
		}
	}
}

int main () {
	read ();
	
	dijkstra ();
	
	for (int i = 2; i <= n; ++i){
		if(cost[i]==2147483646){out<<"0 ";continue;}
		out << cost[i] << ' ';
	}
	out << '\n';
	
	return 0;
}