#include <queue>
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
vector<pair<int,int>> g[50001];
int d[50001];
struct DereferenceCompareNode
{
	bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) const
	{
		return lhs.second < rhs.second;
	}
};
void dijk(){
	int x;
	d[1] = 0;
	priority_queue<pair<int, int>,vector<pair<int,int>>,DereferenceCompareNode> q;
	q.push(pair<int, int>(1, 0));
	while (!q.empty()){
		x = q.top().first;
		q.pop();
		for (auto& i : g[x])
		if (d[i.first]<0 || d[i.first]>d[x] + i.second){
			d[i.first] = d[x] + i.second;
			q.push(i);
		}
	}
}
int main(){
	ifstream f("dijkstra.in");
	ofstream of("dijkstra.out");
	int a, b, c,N,M;
	memset(d, -1, sizeof(d));
	f >> N >> M;
	for (int i = 0; i < M; ++i){
		f >> a >> b >> c;
		g[a].push_back(pair<int, int>(b, c));
	}
	dijk();
	for (int i = 2; i <= N; ++i)
		of << d[i] << " ";
}