#include <iostream>
#include <fstream>
#include <queue>
#define pii pair<int , int >
#define NMAX 50005
#define INF 0x3f3f3f3f
#include <string.h>
std::ifstream in("bellmanford.in");
std::ofstream out("bellmanford.out");
using namespace std;
vector< pii > v [NMAX];
queue < int > q;
int cost[NMAX],tati[NMAX],n,m,cicl;

void bellman(int nod)
{
    memset(cost,INF,sizeof(cost));
    cicl=false;
    cost[nod]=0;
    tati[nod]=1;
    q.push(nod);
    while(!q.empty())
    {
        int next = q.front();
        q.pop();
        if(tati[next]>n)
        {
            cicl=true;
            return ;
        }
        if(cost[next] != INF)
        {
            for(int i=0; i<v[next].size(); i++)
            {
                if(cost[v[next][i].first] > v[next][i].second + cost[next])
                {
                    cost[v[next][i].first]=v[next][i].second + cost[next];
                    q.push(v[next][i].first);
                    tati[v[next][i].first]++;
                }
            }
        }
    }
}
int a,b,c;
int main()
{
    in>>n>>m;
    for(int i=0; i<m; i++)
    {
        in>>a>>b>>c;
        v[a].push_back({b,c});
    }
    bellman(1);
    if(cicl)
    {
        out<<"Ciclu negativ!";
    }
    else
    {
        for(int i=2; i<=n; i++)
        {
            out<<cost[i]<<" ";
        }
    }
    return 0;
}