#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;

const int nodes = 50003;

int n, m;
bool negCycle;
vector < pair < int, int> > where[nodes];
vector <int> dist(nodes, 0x3f3f3f3f), whatAp(nodes, 0);
vector <bool> alreadySeen(nodes, 0);
queue < int > q;

int main(){
    ifstream fin ("bellmanford.in");
    ofstream fout ("bellmanford.out");
    fin >> n >> m;
    for (int adj = 0 ; adj < m ; ++ adj){
            int x, y, cost;
            fin >> x >> y >> cost;
            where[x].push_back({y, cost});
    }
    q.push(1);
    dist[1] = 0;
    alreadySeen[1 ] = 1;
    whatAp[1] = 1;
    while (!q.empty() && !negCycle ) {
            int now = q.front();
            q.pop();
            alreadySeen[now ] = false;
            for (const auto &it : where[now])
                if (dist[now] + it.second < dist[it.first] ){
                  dist[it.first] = dist[now] + it.second;
                  whatAp[it.first]++;
                  negCycle = whatAp[it.first] >= n;
                  if (!alreadySeen[it.first])
                  q.push(it.first), alreadySeen[it.first] = 1;
                        }
                  }
    if (negCycle)
      fout << "Ciclu negativ!";
    else
    for (int i = 2; i <= n ; i++)
        fout << dist[i] << " ";
    return 0;
}