#include <iostream>
#include <fstream>
#include <string>

using namespace std;

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

#define nmax 50005
#define mmax 250005

struct nod
{
	int info,cost;
	nod *next;
} *lista[nmax], *p;


int n,m,dist[nmax],pred[nmax];

int bellman(int);



int main()
{
	int i,j,c,x;

	in>>n>>m;

	while(in>>i>>j>>c)
	{
		p= new nod;
		p->info= j;
		p->cost= c;
		p->next= lista[i];
		lista[i]= p;
	}
	
	x= bellman(1);
	if( x == -1)
		out<<"Ciclu negativ!";
	else
		for(i=2;i<=n;i++)
			out<< dist[i]<<" ";



        
    in.close();
    out.close();

	return 0;
}


int bellman(int node)
{
	int i,j;

	nod *q;

	for(i=1;i<=n;i++)
		if(i == node)
			dist[i]= 0;
		else
			dist[i]= 999999;
	
	for(j=1;j<n;j++)
		for(i=1;i<=n;i++)
		{
			q= lista[i];

			while(q)
			{
				if(dist[i] + q->cost < dist[q->info])
				{
					dist[q->info]= dist[i]+ q->cost;
					pred[q->info]= i;
				}
				q= q->next;
			}
		}

		for(i=1;i<=n;i++)
		{
			q= lista[i];

			while(q)
			{
				if(dist[i] + q->cost < dist[q->info])
				{
					return -1;
				}
				q= q->next;
			}
		}
		
		return 1;
}