#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stdlib.h>

using namespace std;

const char iname[] = "bellmanford.in";
const char oname[] = "bellmanford.out";

ifstream fin(iname);
ofstream fout(oname);

int n, m, x, y, i, c;
vector<pair <int, int> > Gr[50005];
queue<int> Q;
int d[50005], ap[50005];

void bellman()
{
	int pr, i;
	Q.push(1);
	d[1] = 0; for(i = 2; i <= n; i ++) d[i] = 2891829;
	while(!Q.empty())
	{
		pr = Q.front(); ap[pr]++; if(ap[pr] >= n) fout << "Ciclu negativ!\n", exit(0);
		Q.pop();
		for(vector<pair <int, int> >::iterator it = Gr[pr].begin(); it != Gr[pr].end(); ++it)
		{
			if(d[it -> first] > d[pr] + it -> second)
			{
				d[it -> first] = d[pr] + it -> second;
				Q.push(it -> first);
			}
		}
	}
}


int main()
{
	fin >> n >> m;
	for(i = 1; i <= m; i ++)
	{
		fin >> x >> y >> c;
		Gr[x].push_back(make_pair(y, c));
	}
	
	bellman();
	for(i = 2; i <= n; i++)
		fout << d[i] << " ";
	return 0;
}