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

using namespace std;
ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");
const int inf = (1<<31)-1;
int n, m;
vector<int>dist;
vector<pair<int, pair<int,int>>> muchii;

void bellman_ford(int n, int m, int s){
    dist.assign(n+1, inf);
    dist[s] = 0;
    for(int i=1; i<n; i++){

        for (auto m:muchii) {
            int x = m.first;
            int y = m.second.first;
            int w = m.second.second;
            if (dist[x] == inf)
                continue;
            if (dist[y] > dist[x] + w){
                dist[y] = dist[x] + w;
            }

        }
    }
    bool cn = false;
    for (auto m:muchii) {
            int x = m.first;
            int y = m.second.first;
            int w = m.second.second;
            if (dist[y] > dist[x] + w){
                cn = true;
                break;
            }

        }
    if (cn) {
        cout<<"Ciclu negativ!";
    }
    else {
        for ( int i =2; i <=n; i++) {
            cout<<dist[i]<<" ";
        }
    }

}

int main()
{
  cin>>n>>m;
  for (int i = 0; i<m; i++){
    int x,y,w;
    cin>>x>>y>>w;
    muchii.push_back({x, {y, w}});
  }
  dist.assign(n+1, 0);
  bellman_ford(n, m, 1);
  return 0;
}