#include <iostream>
#include <fstream>
#include <algorithm>
#include <queue>

using namespace std;

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

const int INF = 0x3f3f3f3f;

struct edg{
	int b, d;
};

struct nod{
	int a, d;
	bool operator<(const nod &rhs)const{
		if(d != rhs.d){
			return d < rhs.d;
		}else{
			return a < rhs.a;
		}
	}
};

int n, m;
vector<edg> gra[50041];

int dst[50041];
priority_queue<nod> pq;

int main(){
	// ios_base::sync_with_stdio(false);
	
	fin >> n >> m;
	for(int i = 0; i < m; ++i){
		int a, b, d;
		fin >> a >> b >> d;
		gra[a].push_back({b,d});
	}
	
	for(int i = 2; i <= n; ++i)dst[i] = INF;
	
	pq.push({1,0});
	while(!pq.empty()){
		auto nd = pq.top();
		pq.pop();
		int a = nd.a;
		
		if(nd.d > dst[a])continue;
		
		for(auto ed : gra[a]){
			int b = ed.b;
			int d = ed.d;
			if(dst[a]+d < dst[b]){
				dst[b] = dst[a]+d;
				pq.push({b,dst[b]});
			}
		}
	}
	
	for(int i = 2; i <= n; ++i){
		fout << dst[i] << " ";
	}
	
	return 0;
}