#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#define maxc 50100
#define inf 0x3f3f3f3f
using namespace std;

int n,m,x,y,dist[maxc],nrd[maxc],c;

vector < pair <int ,int > > G[maxc];
queue<int > q;

bool ok;


void read()
{
    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",&x,&y,&c);
        G[x].push_back(make_pair(y,c)); ///creez graful
    }

    for (int i=1;i<=n;++i)
        dist[i]=inf; ///initializez distantele


    dist[1]=0;
    q.push(1);
}

void bellman()
{
    read();

    while (!q.empty())
    {
        int nod = q.front();
        q.pop();

        for (vector < pair <int ,int > > ::  iterator it= G[nod].begin(); it!=G[nod].end();++it)
        {
            if (dist[it->first]>dist[nod]+it->second)
                {
                    if (nrd[it->first] > n)
                    {
                        ok=true;
                        break;
                    }
                    else
                    {
                        dist[it->first]=dist[nod]+it->second;
                        q.push(it->first);
                        ++nrd[it->first];
                    }

                }

        }
    }

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

int main()
{
    bellman();
    return 0;
}