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

using namespace std;
ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");
const int inf = (1<<31)-1;
int n, m;
vector<int>dist;
vector<int> viz;
vector<pair<int, pair<int,int>>> muchii;
vector<vector<pair<int,int>>> adj_list;
void bellman_ford(int n, int m, int s){
    dist.assign(n+1, inf);
    viz.assign(n+1, 0);
    vector<int> lungime(n+1, 0);
    queue<int> q;
    viz[s] = 1;
    dist[s] = 0;
    q.push(s);
    while (!q.empty()){
        int x = q.front();
        q.pop();
        viz[x] = 0;

        for (auto m: adj_list[x]) {

            int y = m.first;
            int w = m.second;
            if (dist[x] == inf)
                continue;
            if (dist[y] > dist[x] + w){
                dist[y] = dist[x] + w;
                lungime[y] = lungime[x] + 1;
                if (lungime[y] > n-1)
                    {cout<<"Ciclu negativ";
                    return;}

                if (viz[y] != 1){

                    q.push(y);
                    viz[y] = 1;
                }
            }


        }

    }

    for ( int i =2; i <=n; i++) {
        cout<<dist[i]<<" ";
    }


}

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