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

#define NMax 50001
#define MMax 250001
#define inf 2100000000

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

struct muchie{int x,y,val;};

int n,m;
int drum[NMax];

vector<int> v[NMax],w[NMax];
queue<int> cd,cd2;

void init()
{
    int i;
    drum[1]=0;
    for(i=2;i<=n;i++) drum[i]=inf;
    cd.push(1);
}

void bellmanford()
{
    int i,j,e,s;
    for(j=1;j<=n;j++)
    {
        if(j%2==1) while(!cd.empty())
        {
            s=cd.front();
            cd.pop();
            e=v[s].size();
            for(i=0;i<e;i++)
            {
                if(drum[ v[s].at(i) ] > drum[s] + w[s].at(i))
                {
                    drum[ v[s].at(i) ] = drum[s] + w[s].at(i);
                    cd2.push(v[s].at(i));
                }
            }
        }
        else while(!cd2.empty())
        {
            s=cd2.front();
            cd2.pop();
            e=v[s].size();
            for(i=0;i<e;i++)
            {
                if(drum[ v[s].at(i) ] > drum[s] + w[s].at(i))
                {
                    drum[ v[s].at(i) ] = drum[s] + w[s].at(i);
                    cd.push(v[s].at(i));
                }
            }
        }
    }
}

int ciclu()
{
    if(!cd.empty() && !cd2.empty()) return 0;
    return 1;
}

int main()
{
    int i,ok,a,b,c;

    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>a>>b>>c;
        v[a].push_back(b);
        w[a].push_back(c);
    }

    init();
    bellmanford();
    ok=ciclu();

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

    f.close();
    g.close();
    return 0;
}