#include <bits/stdc++.h>

using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
int n,m,d[50005];
struct muchie
{
    int a,b,c;
}e[50005];
int main()
{
    in>>n>>m;
    for(int i=1;i<=m;i++)
        in>>e[i].a>>e[i].b>>e[i].c;
    d[1]=0;
    for(int i=2;i<=n;i++) d[i]=1e6;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
           if(d[e[j].a]+e[j].c<d[e[j].b])
             d[e[j].b]=d[e[j].a]+e[j].c;
    for(int i=1;i<=m;i++)
        if(d[e[i].a]+e[i].c<d[e[i].b])
        {
             out<<"Ciclu negativ!";
             return 0;
        }
    for(int i=2;i<=n;i++) out<<d[i]<<" ";
    return 0;
}