#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

struct bell
{
    int nod,cost;
};

const int nmax = 50005, inf = 2000000006;
int n, m, d[nmax], cnt[nmax], nod, Nnod, cost;
bool viz[nmax], ok;
vector < bell > L[nmax];
queue <int> Q;
 
int main()
{
    int player_unu=0;

    in>>n>>m;
    for(int i = 1; i <= m; i++)
    {
		int x;
		bell aux;
        in>>x>>aux.nod>>aux.cost;

        L[x].push_back(aux);
    }

    for(int i = 2; i <= n; i++)
		d[i] = inf;

    viz[1] = cnt[1] = 1;
    Q.push(1);
    while(!Q.empty () && ok==0)
    {
        nod = Q.front();
        viz[nod] = 0;
        Q.pop();
        for(int i = 0; i<L[nod].size(); i++)
        {
            Nnod = L[nod][i].nod;
            cost = L[nod][i].cost;

            if(d[Nnod]>d[nod] + cost)
            {
                d[Nnod] = d[nod] + cost;
                if(!viz[Nnod])
                {
                    viz[Nnod] = 1;
                    cnt[Nnod]++;
					
                    if(cnt[Nnod]>n)
						ok = 1;

                    Q.push(Nnod);
                }
            }
        }
    }

    if(ok==1)
		out<<"Ciclu negativ!";
    else 
		for(int i = 2; i<=n; i++) 
			out<<d[i] << " ";
    out<<"\n";

    return player_unu;
}