#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
#define pb push_back
#define nmax 50010
#define inf 0x3f3f3f3f
using namespace std;

int n,m1,d[nmax],cnt[nmax];
bool inq[nmax];
vector< pair < int,int> > m[nmax];
queue<int> c;

int solve()
{
    int nod,neg=false;
    vector< pair<int,int> >::iterator it;
    memset(d,inf,sizeof(d));
    memset(inq,false,sizeof(inq));

    d[1]=0;
    c.push(1); inq[1]=true;

    while(!c.empty() )
    {
        nod=c.front();
        c.pop();
        inq[nod]=false;
        for(it=m[nod].begin();it!=m[nod].end();it++)
            if(d[nod]+ it->second< d[ it->first ] )
            {
                d[it->first]=d[nod]+it->second;
                if(!inq[it->first])
                {
                    if(cnt[it->first]>n) neg=true;
                    else
                    {
                        c.push(it->first);
                        inq[it->first]=true;
                        cnt[it->first]++;
                    }
                }
            }
    }
    return neg;
}


int main()
{
    int n1,n2,cost;
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d%d",&n,&m1);
    for(;m1;m1--)
    {
        scanf("%d%d%d",&n1,&n2,&cost);
        m[n1].pb(make_pair(n2,cost));
    }
    if(!solve())
       for(int i=2;i<=n;i++) printf("%d ",d[i]);
        else printf("Ciclu negativ!\n");
    fclose(stdin);
    fclose(stdout);
    return 0;
}