#include <fstream>
#include <vector>
#include <queue>
#define oo 2000000000

using namespace std;

vector< pair<int, short> > L[50005];

int d[50005];
int bagat[50005];
bool in[50005];
queue<int> q;

int main()
{
    ifstream f("bellmanford.in");
    ofstream g("bellmanford.out");

    int n, m, x, y, c;
    f >> n >> m;
    for(int i = 2; i <= n; i ++) d[i] = oo;
    for(; m; m --) {
        f >> x >> y >> c;
        L[x].push_back({y, c});
    }

    q.push(1);
    while(!q.empty()) {
        int v = q.front(); q.pop();
        in[v] = false;
        for(int i = 0; i < L[v].size(); i ++) {
            int act = L[v][i].first;
            int ct = L[v][i].second;
            if(d[act] > d[v] + ct) {
                if(!in[act]) {
                    if(bagat[act] > n) {
                        g << "Ciclu negativ!\n";
                        return 0;
                    }
                    q.push(act);
                    in[act] = true;
                    bagat[act] ++;
                }
                d[act] = d[v] + ct;
            }
        }
    }
    for(int i = 2; i <= n; i ++)
        g << d[i] << " ";
    g << "\n";
    return 0;
}