#include<cstdio>
#include<vector>
#include<set>
#define inf 0xfffffff
using namespace std;

struct muchie	{int y, c;};
struct nod {int n, c;};
vector <muchie> muchii[50001];
vector <int> cost;
char buff[8192];
int n, m, poz;

void ReadBuff(){fread (buff, 1, 8192, stdin); poz = 0;}

void citeste(int &nr){
	nr = 0;
	while (buff[poz] < '0' || buff[poz] > '9')
		if (++poz == 8192) ReadBuff();
	while (buff[poz] >= '0' && buff[poz] <= '9'){
		nr = nr * 10 + (buff[poz] - '0');
		if (++poz == 8192) ReadBuff();
	}
}

struct compara{
	bool operator()(nod n1, nod n2)	const
		{return n1.c < n2.c;}
};
multiset <nod, compara> heap;

int main(){
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	citeste(n); citeste(m);
	int i, x, y, c;
	
	for (i = 0; i < m; i++){
		citeste(x); citeste(y); citeste(c);
		muchii[x].push_back( (muchie){y, c} );
	}
	cost.assign(n+1, inf);
	cost[1] = 0;
	heap.insert( (nod){1, 0} );
	
	while (!heap.empty()){
		multiset<nod, compara>::iterator it = heap.begin();
		int x = (*it).n;
		
		for (i = 0 ;i < (int)muchii[x].size(); i++){
			y = muchii[x][i].y;
			c = muchii[x][i].c;
			if (cost[y] > cost[x] + c){
				cost[y] = cost[x] + c;
				heap.insert( (nod){y, cost[y]} );
			}
		}
		heap.erase(it);
	}
	
	for (i = 2; i<=n; i++) printf("%d ", cost[i] != inf ? cost[i] : 0);
	return 0;
}