#include<cstdio>
#include<vector> 
#include<queue>
#define inf 0xfffffff
#define Check() if (++pozitie == 8192){fread (buff, 1, 8192, stdin); pozitie = 0;}

using namespace std;
struct arc {int nod, cost;};

int n, m, pozitie;
vector < vector <arc> > L(50001);
vector <int> dmin;
queue<int> q;
char buff[8192];

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

void Dijkstra(int s){
	int i;
	dmin[s] = 0; q.push(s);
	
	while (!q.empty()){
		s = q.front();
		for(i = 0; i < (int)L[s].size(); i++)
			if(dmin[L[s][i].nod] >  dmin[s] + L[s][i].cost){
				dmin[L[s][i].nod] = dmin[s] + L[s][i].cost;
				q.push(L[s][i].nod);
			}
		q.pop();
	}
}

int main(){
	int i, x, y, c;
	
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	citeste(n); citeste(m);
	
	for(i = 1; i <= m; i++){
		citeste(x); citeste(y); citeste(c);
		L[x].push_back( (arc) {y, c});
	}
	dmin.assign(n+1, inf);
	Dijkstra(1);
	for(i = 2; i <= n; i++) printf("%d ", dmin[i] != inf ? dmin[i] : 0);
	
	return 0;
}