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

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

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

void bellmanford()
{
  for(int i = 2;i <= n;++i)
    dist[i] = oo;
  queue<int> q;
  q.push(1);

  while(!q.empty())
  {
    int first = q.front();

    for(auto it : graf[first])
      if(dist[it.neigh] > dist[first] + it.cost)
        {
          dist[it.neigh] = dist[first] + it.cost;
          if(!viz[it.neigh]) q.push(it.neigh);
          viz[it.neigh] = true;
          number[it.neigh]++;
          if(number[it.neigh] >= n)
            {
              g<<"Ciclu negativ!";
              return;
            }
        }   
    q.pop();
    viz[first] = false;
  }
  for(int i = 2;i <= n;++i)
    g<<dist[i]<<" ";
}

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