#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
using namespace std;

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

const int NMAX=50001;
const int inf=1<<29;

vector < pair<int, int> > G[NMAX];
vector < pair<int, int> > ::iterator it;
queue <int> Q;
vector < int > dist(NMAX,inf);

bool vizitat[NMAX];

int x, y, c, i, j, m, n, nr_coada[NMAX];

int main()
{
    fin>>n>>m;
    for(i=1; i<=m; i++)
    {
        fin>>x>>y>>c;
        G[x].push_back({y,c});
    }
    dist[1]=0;
    Q.push(1);
    vizitat[1]=true;
    int ciclu_negativ=0;
    while(!Q.empty() && !ciclu_negativ)
    {
        int curr=Q.front();
        Q.pop();
        vizitat[curr]=0;
        for(it=G[curr].begin(); it!=G[curr].end(); it++)
        {
            if(dist[it->first]>dist[curr]+it->second)
            {
                dist[it->first]=dist[curr]+it->second;
                if(vizitat[it->first]==0)
                {
                    vizitat[it->first]=1;
                    if(nr_coada[it->first]>n)
                    {
                        ciclu_negativ=true;
                    }
                    else
                    {
                        Q.push(it->first);
                        nr_coada[it->first]++;
                    }
                }
            }
        }
    }
    if(ciclu_negativ)
    {
        fout<<"Ciclu negativ!";
    }
    else
    {
        for(int i=2; i<=n; i++)
            fout<<dist[i]<<" ";
    }
    return 0;
}