#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string.h>
#include <stdio.h>
 
using namespace std;
 
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
 
const int MAXN = 50005;
const int INF =  20005;
 
int n, m, a, b, c;
vector <pair <int, int> > d[MAXN];
int dist[MAXN];
 
void read(){
	in >> n >> m;
	for(int i = 0; i < m; ++i){
		in >> a >> b >> c;
		d[a].push_back(make_pair(b, c));
	}
}
 
void dijkstra(){
	bool viz[MAXN];
	queue <int> q;
 
	memset(dist, INF, sizeof(dist));
	memset(viz, false, sizeof(viz));
 
	dist[1]=0;
	viz[1]=true;
	q.push(1);
	while(!q.empty()){
		int nod = q.front();
		q.pop();
		viz[nod] = false;
		for( vector <pair <int, int> > ::iterator it = d[nod].begin(); it != d[nod].end(); ++it){
			if(dist[nod] + it->second < dist[it->first]){
				dist[it->first] = dist[nod] + it->second;
				if(!viz[it->first]){
					q.push(it->first);
					viz[it->first] = true;
				}
			}
		}
	}
}
 
void show(){
	for(int i = 2; i <= n; ++i){
		out << (dist[i] < INF ? dist[i] : 0) << " ";
	}
}
 
int main(){
	read();
	dijkstra();
	show();
	return 0;
}