#include <cstdio>
#include <vector>
#include <queue>
#define oo 1000000000
#define N 50003
using namespace std;
struct nod
{
    int x,c;
};
vector <nod> a[N];
vector <nod>::iterator it;
queue <int> q;
int v[N],d[N],is[N];
int n,m;
void R()
{
    nod r;
    int y;
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(int i=1; i<=m; i++)
    {
        scanf("%d %d %d",&y,&r.x,&r.c);
        a[y].push_back(r);

    }
}

void Rez()
{
    int i,ok=0,nr;
    q.push(1);
    for(i=2; i<=n; i++)
        d[i]=oo;
    while(!q.empty() && !ok)
    {
        nr=q.front();
        q.pop();
        is[nr]=0;
        for(it=a[nr].begin(); it!=a[nr].end(); it++)
            if(d[it->x]>d[nr]+it->c)
            {
                d[it->x]=d[nr]+it->c;
                if(is[it->x]==0)
                {
                    q.push(it->x);
                    is[it->x]=1;
                }
                v[it->x]++;
                if(v[it->x]>n) ok=1;

            }
    }
    if (ok) printf("Ciclu negativ!");
    else
        for(i=2; i<=n; i++)
        printf("%d ",d[i]);

}
int main()
{
    R();
    Rez();
    return 0;
}