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

#define N  50000
using namespace std;
int inf = 999999;
int n, m;
int start;
int d[N];
vector < pair <int, int > > v[N];

class cmp
{
	public:
		bool operator ()(int a, int b)
		{
			return d[a]>d[b];
		}
};
void dijstra(int start)
{
	queue<int> q;
	q.push(start);

	while (!q.empty())
	{
		int nod = q.front();
		q.pop();

		for (vector< pair <int , int > >::iterator it = v[nod].begin(); it != v[nod].end(); ++it)
		{
			pair<int , int> crt = *it;
			int nodc = crt.first;
			int cost = crt.second;

			if ( d[nodc] > d[nod] + cost)
			{
				d[nodc] = d[nod] + cost;
				q.push(nodc);
			}

		}
	}
}
int main(void)

{

	fstream f, g;
	f.open("bellmanford.in", ios::in);
	g.open("bellmanford.out",ios::out);

	int i, j;
	int x, y;
	f >> n >> m;
	for (i=1;i<=n;i++)
		d[i]=inf;
//	f >> start;
	for (i = 1; i <= m; i++)
	{
		int x, y, z;
		f >> x >> y >> z;
		v[x].push_back( make_pair (y, z));
	}
	start = 1;
	d[start] = 0;
	dijstra(start);

	for (i = 1; i <= n; i++)
		if (i != start)
			if (d[i]!=inf)
		{
			//g << "Cost de la " << start << " la " << i << " :" << d[i] << '\n';
			g<<d[i]<<' ';
		}
		else
			g<<0<<" ";
}