#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<vector>
#define inf 1<<30
 using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
int coada[2*250001];

typedef struct muchie
{
	int x,cost;
}muchie;
vector<muchie> v_m[50001];
void blf(int *vizitat,int *cost,int n)
{
	int i,p=0,x,v=1,aux;
	vizitat[1]=1;
	coada[v]=1;
	for(i=2;i<=n;i++)
		cost[i]=inf;
	
	while(p!=v)
	{
		p++;
		x=coada[p];
		//se vede pt fiecare drum daca se mai poate imbunatati
		for(i=0;i<v_m[x].size();i++)
		{
			aux=v_m[x][i].x;
			//comparam costurile - daca este mai mic
			if(cost[x]+v_m[x][i].cost<cost[aux])
			{
				cost[aux]=cost[x]+v_m[x][i].cost;
				//vedem daca nu am ajuns la un ciclu
				if(vizitat[aux]>n && cost[aux]<0)
				{
					out<<"Ciclu negativ!";
					return ;
				}
				vizitat[aux]++;
				v++;
				//il adaug in coada
				coada[v]=aux;
			}
		}
	}
	for(i=2;i<=n;i++)
		if(cost[i]==inf)
			out<<"0\n";
		else
			out<<cost[i]<<"\t";
}
int main()
{
	int x,*cost,i,n,m,*vizitat;
	muchie t;
	in>>n>>m;
	vizitat=( int *)malloc((n+1)*sizeof( int ));
	cost=( int *)malloc((n+1)*sizeof( int ));
	cost[1]=0;
	//citire
	for(i=1;i<=m;i++)
	{
		in>>x>>t.x>>t.cost;
		v_m[x].push_back(t);
	}

	blf(vizitat,cost,n);
	free(vizitat);
	free(cost);
	return 0;
}