using namespace std;
#include<fstream>
#include<queue>
#include<vector>
#include<utility>

#define NN 50001
#define INF 0x3f3f3f3f
#define mp make_pair
#define pb push_back
#define ff first
#define ss second

vector<pair<int,int> >G[NN];
queue<int>Q;
vector<int>d(NN,INF);
ofstream out("bellmanford.out");

int n;

void read();
int bmf(int);

int main()
{
	read();
	bmf(1);
		if(!bmf(1))
		out<<"Ciclu negativ";
	else
	for(int i=2;i<=n;i++)
		out<<(d[i]==INF?0:d[i])<<" ";
	return 0;
}

void read()
{
	ifstream in("bellmanford.in");
	int m;
	in>>n>>m;
	int i,j,c;
	for(;m;--m)
	{
		in>>i>>j>>c;
		G[i].pb(mp(j,c));
	}
}

int bmf(int start)
{
	d[start]=0;
	Q.push(start);
	while(!Q.empty())
	{
		int k=Q.front();
			for(int i=0;(int)i<G[k].size();++i)
				if(d[G[k][i].ff]>d[k]+G[k][i].ss)
				{
					d[G[k][i].ff]=d[k]+G[k][i].ss;
					Q.push(G[k][i].ff);
				}
				else
					if(d[G[k][i].ff]>0&&d[k]<0)
						return 0;
					Q.pop();
	}
}