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

struct NOD{ int y,cost; };
const int NMAX=50001;
const int INF=1<<30;

vector<NOD> v[NMAX];
queue<int> q;
int d[NMAX];
bool inq[NMAX];
int nrq[NMAX];

int main()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	int n,m,x,y,cost,i;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&cost);
		v[x].push_back((NOD){y,cost});
	}
	
	for(i=1;i<=n;i++)
		d[i]=INF;
	q.push(1);
	d[1]=0;
	
	while(!q.empty())
	{
		x=q.front();
		q.pop();
		inq[x]=false;
		for(size_t i=0;i<v[x].size();i++)
		{
			y=v[x][i].y;
			if(d[x]+v[x][i].cost<d[y])
			{	
				d[y]=d[x]+v[x][i].cost;
				if(!inq[y])
				{
					q.push(y);
					nrq[y]++;
					inq[y]=true;
					if(nrq[y]==n)
					{
						printf("Ciclu negativ!");
						return 0;
					}
				}
			}
		}
	}
	for(i=2;i<=n;i++)
		printf("%d ",d[i]);
	return 0;
}