#include <fstream>
#include <climits>
#include <vector>
#include <queue>

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

bool cycle_exists;
int n, m, x, y, cost;
int d[50005], node_visitor[50005], f[50005];
vector<pair<int, int> > L[50005];
queue<int> que;

int main(){
    fin >> n  >> m;
    while (m--){
        fin >> x >> y >> cost;
        L[x].push_back(make_pair(y, cost));
    }
    for (int i=0; i<=n; i++){
        d[i] = INT_MAX;
    }
    que.push(1);
    f[1] = 1;
    d[1] = 0;
    while (!que.empty()){
        int node = que.front();
        que.pop();
        f[node] = 0;
        for (auto it : L[node]){
            //fout << node << ' ' << it.first << ' ' << it.second << '\n';
            if (d[it.first] > d[node] + it.second){
                d[it.first] = d[node] + it.second;

                node_visitor[it.first]++;
                if (node_visitor[it.first] == n) { // cycle
                    cycle_exists = true;
                    fout << "Ciclu negativ!";
                    return 0;
                }

                if (f[it.first] == 0){
                    f[it.first] = 1;
                    que.push(it.first);
                }
            }
        }
    }
    for (int i=2; i<=n; i++){
        fout << d[i] << ' ';
    }
    return 0;
}