#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

const int INF = 2000000000;
const int N = 50001;

struct dstn
{
	int nod_dest,d_muchie;
};

vector<dstn> vecin[N]; int n;
queue<int> coada;
bool e_in_coada[N];
int nr_puneri_coada[N];//de cate ori a fost pus in coada.
int d[N];//costul nodului

void citire()
{
	int m,a,b,c;
	scanf("%d%d",&n,&m);
	for (int i = 1; i <= m; ++i)
	{
		scanf("%d%d%d",&a,&b,&c);
		vecin[a].push_back((dstn){b,c});
	}
}

void initializare_bellman_ford()
{
	for (int i = 2; i <= n; ++i)
		d[i] = INF;
	coada.push(1);
	e_in_coada[1] = true;
	nr_puneri_coada[1] = 1;
}

void bellman_ford()
{
	int nod,destinatie,distanta_noua;
	initializare_bellman_ford();
	while (!coada.empty())
	{
		nod = coada.front();
		for (unsigned int i = 0; i < vecin[nod].size(); ++i)
		{
			destinatie = vecin[nod][i].nod_dest;
			distanta_noua = d[nod] + vecin[nod][i].d_muchie;
			if (e_in_coada[destinatie])
				continue;
			if (d[destinatie] > distanta_noua)
			{
				d[destinatie] = distanta_noua;
				coada.push(destinatie);
				e_in_coada[destinatie] = true;
				++nr_puneri_coada[destinatie];
				if (nr_puneri_coada[destinatie] == n)
				{
					printf("Ciclu negativ!");
					exit(0);
				}
			}
		}
		e_in_coada[nod] = false;
		coada.pop();
	}
}

void scriere()
{
	for (int i = 2; i <= n; ++i)
		printf("%d ",d[i]);
}

int main()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	citire();
	bellman_ford();//un fel de bfs
	scriere();
	return 0;
}