#include<fstream>
#include<algorithm>
#include<queue>
#include<vector>
#define INF 100000000000000000
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int d[50001], incoada[50001];
queue<int> c;
vector<pair <int, int> > vec[50001];
int main()
{
	int i, x, y, v;
	long long cnt = 0, n, m;
	f >> n >> m;
	for (i = 1; i <= m; i++)
	{
		f >> x >> y >> v;
		vec[x].push_back(make_pair(y, v));
	}
	for (i = 1; i <= n; i++)
		d[i] = INF;
	c.push(1);
	incoada[1] = 1;
	d[1] = 0;
	while (!c.empty() && cnt <= n*m)
	{
		cnt++;
		x = c.front();
		c.pop();
		incoada[x] = 0;
		vector < pair <int, int> >::iterator it;
		for (it = vec[x].begin(); it != vec[x].end();++it)
		{
			if (d[x] + it->second < d[it->first])
			{
				d[it->first] = d[x] + it->second;
				if (!incoada[it->first])
				{
					c.push(it->first);
					incoada[it->first] = 1;
				}
			}
		}
	}
	/*for (i = 1; i <= n; i++)
	{
		vector < pair <int, int> >::iterator it;
		for (it = vec[i].begin(); it != vec[i].end(); ++it)
		{
			g << i << " " << it->first << " " << it->second<<'\n';
		}
		g << '\n';
	}*/
	
	/*if (cnt == n *m + 1)
		g << "Ciclu negativ!";
	else*/
		for (i = 2; i <= n; i++)
			if(d[i]!=INF)g << d[i] << " ";
			else g << 0 << " ";
}