#include <fstream>

using namespace std;
ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");
#define INF 10e18
#define ll long long
struct ura{
    int x,y,c;
};
ura v[250001],muchie;
ll dist[50001];
int main()
{
    int n,m,i,rip,ind;
    dist[1]=0;
    cin>>n>>m;
    for(i=2;i<=n;i++)
        dist[i]=INF;
    for(i=1;i<=m;i++)
    {
        cin>>v[i].x>>v[i].y>>v[i].c;
    }
    for(ind=1;ind<n;ind++)
    for(i=1;i<=m;i++)
    {
        muchie=v[i];
        if(dist[muchie.x]+muchie.c<dist[muchie.y])
            dist[muchie.y]=dist[muchie.x]+muchie.c;
    }
    rip=0;
    for(i=1;i<=m;i++)
    {
        muchie=v[i];
        if(dist[muchie.x]+muchie.c<dist[muchie.y])
            rip=1;
    }
    if(rip)
        cout<<"Ciclu negativ!";
    else
    {
        for(i=2;i<=n;i++)
            cout<<dist[i]<<" ";
    }
    return 0;
}