#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#define oo 999999

using namespace std;

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

vector< pair<int,int> > V[50005];
vector< pair<int,int> >::iterator it,sf;
queue <int> Q;
int D[50005],nr[50005];
bool intrat[50005],negativ;
int N,M,x,y,c;
int main()
{
    in>>N>>M;
    while(M--)
    {
        in>>x>>y>>c;
        V[x].push_back( make_pair(y,c) );
    }
    fill(D+2,D+N+1,oo);
    Q.push(1);
    while(!Q.empty())
    {
        x = Q.front();
        Q.pop();
        nr[x]++;
        if(nr[x]==N) negativ = true;
        intrat[x] = false;
        for(it=V[x].begin(),sf=V[x].end();it<sf;++it)
        {
            y = it->first,c=it->second;
            if(D[y]>D[x]+c)
            {
                D[y] = D[x]+c;
                if(intrat[y]==false)
                {
                    Q.push(y);
                    intrat[y]=true;
                }
            }
        }
    }
    if(negativ)
        out<<"Ciclu negativ!";
    else for(int i=2;i<=N;i++)
            out<<(D[i]==oo?0:D[i])<<' ';
    out<<'\n';
    return 0;
}