#include <fstream>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

#define INF 0xfffff

int N,M;
vector<int> d;
vector<int> viz;
vector<int> incoada;
vector< vector<pair<int,int> > > G;
queue<int> coada;

bool BellmanFord(int nod)
{
    d[nod]=0;
    coada.push(nod);
    incoada[nod]=1;

    while(coada.empty()==0)
    {
        int aux=coada.front();
        viz[aux]++;
        if(viz[aux]>=N)
            return false;

        coada.pop();
        incoada[aux]=0;

        for(pair<int,int> per: G[aux])
        {
            int x=aux;
            int y=per.first;
            int cost=per.second;
            if(d[y]>d[x]+cost)
            {
                d[y]=d[x]+cost;
                if(!incoada[y])
                    coada.push(y);
            }
        }
    }
    return true;
}

int main()
{
    fin>>N>>M;
    d.resize(N+1,INF);
    viz.resize(N+1,0);
    incoada.resize(N+1,0);
    G.resize(N+1);

    int i;
    for(i=1;i<=M;i++)
    {
        int x, y, cost;
        fin>>x>>y>>cost;
        G[x].push_back(make_pair(y,cost));
    }
    if(BellmanFord(1)==1)
    {
        for(i=2;i<=N;i++)
            fout<<d[i]<<" ";
    }
    else
        fout<<"Ciclu negativ!";
    return 0;
}