#include <cstdio>
#include <vector>
#include <bitset>
#include <queue>
using namespace std;
const int NMAX=50004;
const int oo=0x3f3f3f3f;
vector < pair<int,int> > L[NMAX];
int n;

void citire()
{
	FILE *fin=fopen("bellmanford.in","r");
	int m,x,y,c;
	fscanf(fin,"%d%d",&n,&m);
	while (m--)		
	{
		fscanf(fin,"%d %d %d",&x,&y,&c);
		L[x].push_back(make_pair(y,c));		
	}
	fclose(fin);
}

int main()
{
	citire();
	bool cneg=0;
	bitset <NMAX> viz(false); 
	vector <int> dist(NMAX,oo), nviz(NMAX,0); 
	queue <int> Q;
	Q.push(1); viz[1]=1; dist[1]=0;
	while (!Q.empty() && !cneg)
	{
		int x=Q.front(); Q.pop(); viz[x]=0;
		vector < pair<int,int> > ::iterator i;
		for (i= L[x].begin(); i != L[x].end(); ++ i)
		 if (dist[i->first] > dist[x]+ i->second) 
			{
			 int j=i->first;
			 dist[j]=dist[x]+i->second;
			 if (!viz[j])
				{
					if (nviz[j]==n) cneg=1;
						else
						{
							nviz[j]++;
							viz[j]=1;
							Q.push(j);
						}
				}
			}		
	}	
	
	FILE *fout=fopen("bellmanford.out","w");	
	if (cneg) { fprintf(fout,"Ciclu negativ!");}
	   else
	   {
		   for (int i=2;i<=n;++i)
			   fprintf(fout,"%d ",dist[i]);
	   }
	fclose(fout);
	return 0;
}