#include <iostream>
#include <fstream>
#include <queue>
#include <cstdlib>
#define N  50016
using namespace std;
int inf = 999999;
fstream f, g;
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];
	}
};
int is_in_queue[N];
int count[N];
void dijstra(int start)
{
	queue<int> q;
	q.push(start);

	while (!q.empty())
	{
		int nod = q.front();
		q.pop();
		is_in_queue[nod] = 0;
		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;
				if (is_in_queue[nodc] == 0)
				{
					q.push(nodc);
					is_in_queue[nodc] = 1;
					count[nodc]++;
					if (count[nodc] > n )
					{
						g << "Ciclu negativ!\n";
						exit(0);
					}
				}

			}

		}
	}
}
int main(void)

{

	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 << " ";
}