#include <stdio.h>
#include <vector>
#include <queue>

#define inf 999999
using namespace std;

int n, m, d[50002];
vector<pair<int, int> > g[50002];
void read(){
	FILE *in;
	in = fopen("dijkstra.in", "r");
	
	fscanf(in, "%d%d", &n, &m);
	for(int i = 0; i < m; i++){
		int x, y, z;
		fscanf(in, "%d%d%d", &x, &y, &z);
		g[x].push_back(pair<int, int> (y, z));
	}
	
	fclose(in);
}

void rez(){
	bool s[50002];
	queue<int> q;
	
	for(int i = 0; i < 50002; i++){
		d[i] = inf;
		s[i] = false;
	}
	
	d[1] = 0;
	q.push(1);
	s[1] = true;
	
	while(!q.empty()){
		int current = q.front();
		q.pop();
		s[current] = false;
		
		for(int i = 0; i < g[current].size(); i++){
			if(d[current] + g[current][i].second < d[g[current][i].first]){
				d[g[current][i].first] = d[current] + g[current][i].second;
				if(!s[g[current][i].first]){
					q.push(g[current][i].first);
					s[g[current][i].first] = true;
				}
			}
		}
	}
}

void write(){
	FILE *out;
	out = fopen("dijkstra.out", "w");
	
	for(int i = 2; i <= n; i++){
		if(d[i] < inf)
			fprintf(out, "%d ", d[i]);
		else 
			fprintf(out, "0 ");
	}
}
int main(){
	read();
	rez();
	write();
}