#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
vector<pair<int,int> >f[50005];
queue<int>q;
long long k,i,m,x,j,g[50005],ct,h1[50005];
const long long inf=1e10;
bool h[50005];
int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%lld%lld",&x,&m);
    for(k=1;k<=m;k++)
    {
        scanf("%lld%lld%lld",&i,&j,&ct);
        f[i].push_back(make_pair(j,ct));
    }
    for(k=2;k<=x;k++)
        g[k]=inf;
    for(q.push(1);!q.empty();)
    {
        k=q.front();
        h[k]=0;
        q.pop();
        for(i=0;i<f[k].size();i++)
        {
            if(g[f[k][i].first]>g[k]+f[k][i].second&&!h[f[k][i].first])
            {
                g[f[k][i].first]=g[k]+f[k][i].second;
                q.push(f[k][i].first);
                h[f[k][i].first]=1;
                h1[f[k][i].first]++;
                if(h1[f[k][i].first]==x-1)
                {
                    printf("Ciclu negativ!\n");
                    return 0;
                }
            }
        }
    }
   /* for(k=1;k<=x;k++)
    {
        for(i=0;i<f[k].size();i++)
        {
            if(g[f[k][i].first]>g[k]+f[k][i].second)
            {
                printf("Ciclu negativ!\n");
                return 0;
            }
        }
    }*/
    for(k=2;k<=x;k++)
        printf("%lld ",g[k]);
    printf("\n");
    return 0;
}