#include <fstream>
#include <queue>
#include <vector>
using namespace std;

ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");

#define INF 0x3f3f3f3f
#define MAXN 50005

struct rct
{
    int nod;
    int cost;
}crt;

vector<rct> graf[MAXN];
queue<int> coada;
int n,m,i,j,x,y,z,ok;
int d[MAXN], nrc[MAXN];
bool negativ;

int main()
{
    cin >> n >> m;
    for(i=1; i<=m; i++)
    {
        cin >> x >> y >> z;
        crt.nod = y; crt.cost=z;
        graf[x].push_back(crt);
    }

    for(i=1; i<=n; i++)
        d[i] = INF;

    d[1] = 0 ; coada.push(1);
    while(!coada.empty())
    {
        ok = coada.front(); coada.pop();
        for(i=0; i< graf[ok].size(); i++)
        {
            if(d[ graf[ok][i].nod ] > d[ok] + graf[ok][i].cost)
            {
                if( nrc[ graf[ok][i].nod ] > n)
                    negativ = true;
                else
                {
                    d[ graf[ok][i].nod ] = d[ok] + graf[ok][i].cost;
                    nrc[ graf[ok][i].nod ] ++;
                    coada.push( graf[ok][i].nod );
                }

            }
        }

    }
    if(negativ)
        cout<<"Ciclu negativ!";
    else
        for(i=2; i<=n; i++)
            cout<<d[i]<<" ";
    return 0;
}