#include <iostream>
#include <fstream>
#include <vector>
#include <set>

using namespace std;

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

const int INF = 0x3f3f3f3f;

struct muc{
	int no, va;
	bool operator<(const muc &rhs) const{
		if(va != rhs.va){
			return (va < rhs.va);
		}
		return no < rhs.no;
	}
};

int n, m;
vector<muc> gra[50041];
set<muc> se;

int armin[50041];

void drijkstra(){
	for(int i = 2; i <= n; i++){
		armin[i] = INF;
	}
	se.insert({1, 0});
	
	while(!se.empty()){
		auto a = *se.begin();se.erase(se.begin());
		for(const auto &b : gra[a.no]){
			int x = armin[a.no]+b.va;
			if(x < armin[b.no]){
				if(armin[b.no] != INF){
					se.erase({b.no, armin[b.no]});
				}
				armin[b.no] = x;
				se.insert({b.no, x});
			}
		}
	}
}

int maresusta(int a){
	if(a == INF){
		return 0;
	}else{
		return a;
	}
}

int main(){
	fin >> n >> m;
	for(int i = 0; i < m; ++i){
		int a, b, va;
		fin >> a >> b >> va;
		gra[a].push_back({b, va});
	}
	drijkstra();
	for(int i = 2; i <= n; i++){
		fout << maresusta(armin[i]) << " ";
	}
	return 0;
}