#include<cstdio>
#include<vector> 
#include<queue>
#define inf 1<<30

FILE *in = fopen("dijkstra.in","r"), *out = fopen("dijkstra.out","w");
using namespace std;
struct arc {int nod;	int cost;};

int n, m;
vector < vector <arc> > L(50001);
vector <int> dmin(50001, inf);
queue<int> q;

void Dijkstra(int s){
	int i;
	dmin[s] = 0; q.push(s);
	
	while (!q.empty()){
		s = q.front();
		for(i = 0; i < 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;
	
	fscanf(in, "%d %d", &n, &m);
	for(i = 1; i <= m; i++){
		fscanf(in, "%d %d %d", &x, &y, &c);
		L[x].push_back( (arc) {y, c});
	}
	
	Dijkstra(1);
	for(i = 2; i <= n; i++) fprintf(out, "%d ", dmin[i] != inf ? dmin[i] : 0);
	
	return 0;
}