#include<stdio.h>
#include<vector>
using namespace std;
#define inf 2000000000
#define nmax 50002
#define mmax 250002
#define nrmax 1000000
#define f first
#define s second
int n,m,c[nmax],ok[nmax];
vector<int> q;
vector< pair<int,int> > v[nmax];

void sol()
{
    int p,u,i,lim,nod,nr=0;
    p=u=0;
    q.push_back(1);
    while(p<=u)
    {
        nod=q[p];
        ok[nod]=0;
        lim=v[nod].size();
        for(i=0; i<lim; i++)
            if(c[nod]+v[nod][i].s<c[v[nod][i].f])
            {
                c[v[nod][i].f]=c[nod]+v[nod][i].s;
                if(ok[v[nod][i].f]==0)
                {
                    q.push_back(v[nod][i].f);
                    ok[v[nod][i].f]=1;
                    ++u;
                }
                nr++;
            }
        p++;
        if(nr>nrmax)
            break;
    }
}

bool ciclu()
{
    int i,j,lim;
    for(i=1; i<=n; i++)
    {
        lim=v[i].size();
        for(j=0; j<lim; j++)
            if(c[i]+v[i][j].s<c[v[i][j].f])
                return 1;
    }
    return 0;
}

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d%d",&n,&m);
    int i,a,b,cost;
    for(i=1; i<=m; i++)
    {
        scanf("%d%d%d",&a,&b,&cost);
        v[a].push_back(make_pair(b,cost));
    }
    for(i=2; i<=n; i++)
        c[i]=inf;
    sol();
    if(ciclu())
        printf("Ciclu negativ!\n");
    else
        for(i=2; i<=n; i++)
            printf("%d ",c[i]);
    return 0;
}