#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

vector < pair<int, int> > G[50005];
queue <int> Q;
int d[50005],n,m,x,y,c,i,k,ap[50005],viz[50005];

void bf()
{
    vector < pair<int, int> >::iterator it;
    int x;

    fill(d+1,d+n+1,int(2e9));
    d[1]=0;
    ap[1]=1;
    Q.push(1);
    while (!Q.empty())
    {
        x=Q.front();
        viz[x]=0;
        for (it=G[x].begin();it!=G[x].end();++it)
            if (d[it->first]>d[x]+it->second)
            {
                d[it->first]=d[x]+it->second;
                if (!viz[it->first])
                {
                    viz[it->first]=1;
                    Q.push(it->first);
                    ap[it->first]++;
                    if (ap[it->first]==n)
                    {
                        k=1;
                        return;
                    }
                }
            }
        Q.pop();
    }
}

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d %d", &n, &m);
    for (i=1;i<=m;i++)
    {
        scanf("%d %d %d", &x, &y, &c);
        G[x].push_back(make_pair(y,c));
    }
    bf();
    if (k)
        printf("Ciclu negativ!");
    else
        for (i=2;i<=n;i++)
            printf("%d ", d[i]);

    return 0;
}