#include<bits/stdc++.h>
using namespace std;

const int N = 50009;
int n, d[N];
bool visited[N];
vector<pair<int, int>> leg[N];
priority_queue<pair<int , int>, vector<pair<int, int>>, greater<pair<int, int>>> candidates;

ifstream in ("dijkstra.in");
ofstream out("dijkstra.out");
// auto& in = cin;
// auto& out = cout;

void dijkstra() {
	pair<int, int> crt;
	while(!candidates.empty()) {
		crt = candidates.top();
		candidates.pop();
		if(visited[crt.second])	continue;
		// out<<"selected: "<<crt.second<<" with cost: "<<crt.first<<endl;
		d[crt.second] = crt.first;
		for(auto neighbor : leg[crt.second])
			candidates.emplace(crt.first + neighbor.first, neighbor.second);
		visited[crt.second] = true;
	}
}
void show() {
	for(int i=2;i<=n;i++)
		out<<d[i]<<' ';
	out<<endl;
}
int main(){
	int m, a, b, c;
	in>>n>>m;
	for(int i=0;i<m;i++) {
		in>>a>>b>>c;
		leg[a].emplace_back(c, b);
	}
	candidates.emplace(0, 1);
	dijkstra();
	show();
	return 0;
}