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

#define NMax 50005
#define inf 2100000000

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

int n,m;
vector<int> v[NMax],w[NMax];
queue<int> cd[2];
int d[NMax];

void Bellmanford(int ind)
{
    int i,s;
    while(!cd[ind].empty())
    {
        s=cd[ind].front(); cd[ind].pop();
        for(i=0;i<(int)v[s].size();i++) if(d[v[s][i]]>d[s]+w[s][i]) d[v[s][i]]=d[s]+w[s][i],cd[1-ind].push(v[s][i]);
    }
}

int Bellmanford_check(int ind)
{
    int i,s;
    while(!cd[ind].empty())
    {
        s=cd[ind].front(); cd[ind].pop();
        for(i=0;i<(int)v[s].size();i++) if(d[v[s][i]]>d[s]+w[s][i]) return 0;
    }

    return 1;
}

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

    f>>n>>m;

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

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

    cd[1].push(1);

    for(i=1;i<=n;i++) Bellmanford(i%2);

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

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