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

#define NMAX 50005
#define INF 1000000000

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

struct arc {int vf,c;}; ///extremitatea finala si costul sau
vector <arc> G[NMAX];
queue <int> coada;

int n,m,start;
int cmin[NMAX],nr[NMAX];
bool circuit_negativ=0;

void citire()
{
    int x,y,cost;
    arc a;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
            fin>>x>>y>>cost;
            a.vf=y; a.c=cost;
            G[x].push_back(a);
    }
}

int main()
{
    citire();
    ///initializare
    for(int i=1;i<=n;i++) cmin[i]=INF;
    start=1;
    cmin[start]=0;
    coada.push(start);
    while(!coada.empty() && !circuit_negativ)
    {
        int x=coada.front(),i; coada.pop();
        ///parcurg lista de adiacenta a lui x
        for(i=0;i<G[x].size();i++)
            {
                int y=G[x][i].vf;
                int cost=G[x][i].c;
                if(cmin[y]>cmin[x]+cost)
                {
                    cmin[y]=cmin[x]+cost;
                    nr[y]++;
                    if(nr[y]==n)
                        circuit_negativ=1;
                    else
                        coada.push(y);
                }
            }
    }
    if(circuit_negativ) fout<<"Ciclu negativ!" ;
    else
    {
        for(int i=2;i<=n;i++)
            fout<<cmin[i]<<' ';
    }
    return 0;
}