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

std::fstream f("bellmanford.in",std::ios::in);
std::fstream g("bellmanford.out",std::ios::out);

const long long MAX = 9223372036854775807;
const int nrMAX = 50001;

std::vector<std::pair<std::pair<int, int>,int> > distValues;
long long dist[nrMAX];

void init(int &N,int &M);
void solve(int N,int M);

int main()
{
    int N,M;

    init(N,M);
    solve(N,M);

    return 0;
}

void init(int &N,int &M)
{
  f>>N>>M;

  int i,x,y,l;

  dist[1] = 0;
  for(i = 2; i <= N; ++i)dist[i] = MAX;

  for(i = 1; i <= M; ++i)
    {
        f>>x>>y>>l;
        distValues.push_back(std::make_pair(std::make_pair(x,y),l));
    }
}

void solve(int N, int M)
{
  int i,j,src,dest,weight;
  for(i = 1; i<N;++i)
    {
    for(j=0;j<M;++j)
        {
        src = distValues[j].first.first;
        dest = distValues[j].first.second;
        weight = distValues[j].second;

        if(dist[src]!= MAX && (dist[dest]>weight+dist[src]))
            {
            dist[dest] = weight+dist[src];
            }
        }
    }

    for(j=0;j<M;++j)
        {
        src = distValues[j].first.first;
        dest = distValues[j].first.second;
        weight = distValues[j].second;
        if(dist[src]!= MAX && dist[dest]>weight+dist[src])
            {
               g<<"Ciclu negativ!";
               return;
            }
        }

    for(j=2;j<=N;++j)
        {
        g<<dist[j]<<" ";
        }
}