#include <bits/stdc++.h>

#define INF 0x3f3f3f3f
#define pb push_back
#define mp make_pair
#define st first
#define nd second

using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

vector <pair <int, int> > v[50006];
int n, m, a, b, c, d[50006];
pair <int, int> x;

int main(){
	ios::sync_with_stdio(0);
	in.tie(0);
	
	in >> n >> m;
	
	//for(int i = 1; i <= n; i++) d[i] = INF;
	//d[1] = 0;
	memset(d, INF, sizeof d);
	//for(int i = 2; i <= n; i++) d[i] = INF;
	d[1] = 0;
	
	for(int i = 1; i <= m; i++){
		in >> a >> b >> c;
		v[a].push_back(mp(b, c));
	}
	
	set <pair <int, int> > myset;
	
	myset.insert(mp(1, 0));
	
	while(!myset.empty()){
		
		int nodcur = myset.begin()->st;
		int distcur = myset.begin()->nd;	
		myset.erase(myset.begin());
	
		for(vector <pair <int, int> > :: iterator it = v[nodcur].begin(); it != v[nodcur].end(); ++it){
			
			int nodul = it->st;
			int costul = it->nd;
			
			if(d[nodcur] + costul < d[nodul]){
				
				if(d[nodul] != INF){
				//	x.st = nodul;
				//	x.nd = d[nodul];
				//	myset.erase(myset.find(x));
					myset.erase(mp(nodul, d[nodul]));
				}
				
				d[nodul] = d[nodcur] + costul;
			//	x.st = nodul;
			//	x.nd = d[nodul];
			//	myset.insert(x);			
				myset.insert(mp(nodul, d[nodul]));
			}			
			
		}
		
	}
	
	for(int i = 2; i <= n; i++)
		if(d[i] == INF) out << "0 ";
		else out << d[i] << ' ';
	
	return 0;
}