#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 50005;
int start = 1;
int n,m,a,b,c;
vector<pair<int,int>>g[nmax];
int dmin[nmax];
int imp[nmax];

int main()
{
    fin >> n >> m;

    for(int i = 1 ; i <= m ; ++i)
    {
      fin >> a >> b >> c;
      g[a].push_back({b,c});
    }

    for(int i = 1 ; i <= n ; ++i)
      dmin[i] = INT_MAX;
    dmin[start]=0;

    queue<int>q;
    q.push(start);

    while(!q.empty())
    {
      int crt = q.front();
      for(auto it:g[crt])
      {
        if(dmin[crt] + it.second < dmin[it.first])
        {
          q.push(it.first);
          dmin[it.first] = dmin[crt] + it.second;
          imp[it.first]++;
          if(imp[it.first]==n)
          {
            fout << "Ciclu negativ!";
            exit(0);
          }
        }
      }
      q.pop();
    }

    for(int i = 2 ; i <= n ; ++i)
      fout << dmin[i] << ' ';

    return 0;
}