#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");
queue<int> q;
vector<pair<int, int>> v[50002];
int n, m, l, i, x, y, vizitat[50002], costuri[50002], verifica_negativ[50002];
int main()
{
  cin >> n >> m;
  for (i = 1; i <= m; i++)
  {
    cin >> x >> y >> l;
    v[x].push_back({y, l});
  }
  for (i = 2; i <= n; i++)
    costuri[i] = 1000000000;
  costuri[1] = 0;
  q.push(1);
  vizitat[1] = 1;
  while (!q.empty())
  {
    x = q.front();
    q.pop();
    vizitat[x]=0;
    for (i = 0; i < v[x].size(); i++)
    {
      y = v[x][i].first;
      if (costuri[y] > costuri[x] + v[x][i].second)
      {
        costuri[y] = costuri[x] + v[x][i].second;
        if (vizitat[y] == 0)
        {
          verifica_negativ[y]++;
          if (verifica_negativ[y] == n)
          {
            cout << "Ciclu negativ!";
            return 0;
          }
          q.push(y);
          vizitat[y] = 1;
        }
      }
    }
  }
  for (i = 2; i <= n; i++)
    cout << costuri[i] << " ";
}