#include <cstdio>
#include <cstring>
#include <queue>
#define N 50003
#define INF 0x3f3f3f3f
using namespace std;

struct graf
{
    int n, cost;
    graf *next;
};

graf *a[N];
int v[N], d[N], cnt[N];

inline void gadd(int x, int y, int cost)
{
    graf *p=new graf;
    p->n=y;
    p->cost=cost;
    p->next=a[x];
    a[x]=p;
}

int main()
{
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    int n, m, i, x, y, cost, ok=0;
    queue <int> Q;
    graf *p;
    scanf("%d%d", &n, &m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d", &x, &y, &cost);
        gadd(x, y, cost);
    }
    memset(d, INF, sizeof(d));
    Q.push(1);
    v[1]=cnt[1]=1;
    d[1]=0;
    while(!Q.empty()&&!ok)
    {
        x=Q.front();
        Q.pop();
        v[x]=0;
        for(p=a[x];p;p=p->next)
        {
            if(d[x]+p->cost<d[p->n])
            {
                d[p->n]=d[x]+p->cost;
                if(!v[p->n])
                {
                    if(cnt[p->n]>n) ok=1;
                    else
                    {
                        Q.push(p->n);
                        v[p->n]=1;
                        cnt[p->n]++;
                    }
                }
            }
        }
    }
    if(ok) printf("Ciclu negativ!");
    else
    {
        for(i=2;i<=n;i++) printf("%d ", d[i]);
    }
}