#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
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];
bitset<NMax> B[2];
int D[NMax];

int BFord(int ind)
{
    int s,i,ok=1;
    while(!cd[ind].empty())
    {
        s=cd[ind].front();
        cd[ind].pop();
        B[ind][s]=0;

        for(i=0;i<v[s].size();++i) if(D[v[s][i]]>D[s]+w[s][i])
        {
            D[v[s][i]]=D[s]+w[s][i];
            if(!B[1-ind][v[s][i]])
            {
                cd[1-ind].push(v[s][i]);
                B[1-ind][v[s][i]]=1;
                ok=0;
            }
        }
    }

    return ok;
}

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++) BFord(i%2);

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

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