#include <bits/stdc++.h>

using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

struct metro{
    int x,y;
    long long w;
};

vector<metro> edges;

int main()
{
    int n,m; fin>>n>>m;
    vector<long long> dist(n+1,2e10);

    for(int i=1; i<=m; ++i)
    {
        int x,y; long long w;
        fin>>x>>y>>w;
        edges.push_back({x,y,w});
    }

    dist[1]=0;
    for(int i=1; i<n; ++i)
    {
        bool ok=0;
        for(auto edge: edges)
        {
            int x=edge.x; int y=edge.y; long long w=edge.w;
            if(dist[x]!=2e10 && dist[y]>dist[x]+w)
            {
                ok=1;
                dist[y]=dist[x]+w;
            }
        }
        if(ok==0)
            break;
    }

    //check pt ciclu negativ
    for(auto edge: edges)
    {
        int x=edge.x; int y=edge.y; long long w=edge.w;
        if(dist[x]!=2e10 && dist[y]>dist[x]+w)
        {
            fout<<"Ciclu negativ!";
            return 0;
        }
    }

    for(int i=2; i<=n; ++i)
        fout<<dist[i]<<" ";
    return 0;
}