#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <bitset>
#define nmax 50006
#define inf 0x7fffffff;
using namespace std;

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

inline int bellf()
{
    int nod,ciclu=0;
    vector< pair<int,int> >::iterator it;
    for(int i=1;i<=n;i++) d[i]=inf;
    d[1]=0;
    q.push(1); inq[1]=1;
    while(!q.empty())
    {
        nod=q.front(); q.pop(); cnt[nod]++; inq[nod]=0;
        if(cnt[nod]>=n) { ciclu=1; return ciclu; }
        for(it=m[nod].begin();it!=m[nod].end();it++)
            if( d[it->first ]> d[nod]+ it->second)
            {
                d[it->first ]=d[nod]+it->second;
                if(!inq[it->first ]) { q.push(it->first); inq[it->first]=1; }
            }
    }
    return ciclu;
}

int main()
{

    int i,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].push_back( make_pair(n2,cost) );
    }
    if(!bellf())
        for(i=2;i<=n;i++) printf("%d ",d[i]);
    else printf("Ciclu negativ!\n");
    fclose(stdin);
    fclose(stdout);
    return 0;
}