#include <fstream>
#include <queue>
#include <iostream>
#include <cstring>

using namespace std;

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

const int maxn = 50100, inf = 0x0f0f0f;

int n, m, a, b, c, d[maxn];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > heap;
vector<int> vec[maxn], cost[maxn];

void solve()
{
	int val, x;
	
	heap.push(make_pair(0, 1));
	while(heap.size() > 0)
	{
		val = heap.top().first;
		x = heap.top().second;
		heap.pop();
		
		for(int i = 0; i < vec[x].size(); ++i)
		{
			if(d[ vec[x][i] ] > val + cost[x][i])
				d[ vec[x][i] ] = val + cost[x][i], heap.push(make_pair(d[ vec[x][i]], vec[x][i]));
		}
	}
}

int main()
{
	f >> n >> m;
	memset(d, inf, maxn*sizeof(int));
	
	for(int i = 0; i < m; ++i)
	{
		f >> a >> b >> c;
		vec[a].push_back(b);
		cost[a].push_back(c);
	}
	
	solve();
	
	for(int i = 2; i <= n; ++i)
		if(d[i] == inf)
			g << "0\n";
		else
			g << d[i] << "\n";
}