#include <bits/stdc++.h>
#define oo 0x3f3f3f3f
#define edge pair<int, int>
#define node first
#define cost second

using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n, m;
vector<edge> graf[50001];
int number[50001], result[50001];
bool in_q[50001];

void read()
{
  f>>n>>m;
  int x, y, z;
  for(int i = 1;i <= m;++i)
    f>>x>>y>>z, graf[x].push_back(make_pair(y, z));
}

void solve()
{
  memset(in_q, false, sizeof(in_q));

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

  for(int i = 2;i <= n;++i)
    result[i] = oo;
  
  while(!q.empty())
  {
    int nod = q.front();

    for(auto ed : graf[nod])
      if(result[ed.node] > result[nod] + ed.cost)
      {
        result[ed.node] = result[nod] + ed.cost;
        if(!in_q[ed.node]) q.push(ed.node);
        in_q[ed.node] = true;
        ++number[ed.node];

        if(number[ed.node] >= n)
        {
          g<<"Ciclu negativ!";
          return;
        }
      }
    
    in_q[nod] = false;
    q.pop();
  }

  for(int i = 2;i <= n;++i)
    g<<result[i]<<" ";
}

int main()
{
  read();
  solve();
  return 0;
}