#include <bits/stdc++.h>

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

vector < pair<int,int> > mv[50005];
queue <int> q;
vector <int> dist(50005,1000000);
vector <int> cntinq(50005,0);

int main(){
	int n,m,x,y,c,i,negativeCycle;

	fin>>n>>m;

	for(i=1;i<=m;i++){
		fin>>x>>y>>c;
		mv[x].push_back(make_pair(y,c));
	}

	bitset <50005> inq(0);

	dist[1]=0;
	inq[1].flip();
	q.push(1);

	while(!q.empty() && !negativeCycle){
		x=q.front();
		q.pop();

		inq[x]=0;

		for(i=0;i<mv[x].size();i++){
			if(dist[mv[x][i].first]>dist[x]+mv[x[i].second){
				dist[mv[x][i].first]=dist[x]+mv[x][i].second;

				if(!inq[mv[x][i].first]){
					if(cntinq[mv[x][i].first]>n)
						negativeCycle=1;
					else{
						q.push(mv[x][i].first);
						inq[mv[x][i].first]=1;
						cntinq[mv[x][i].first]++;
					}
				}
			}
		}
	}

	if(negativeCycle)
		fout<<"Ciclu negativ!";
    else{
        for(i=2;i<=n;++i)
            fout<<dist[i]<<' ';
    }


    return 0;
}