///https://infoarena.ro/problema/bellmanford
#include<iostream>
#include<fstream>
#include<vector>
#include<tuple>
using namespace std;

vector<tuple<int,int,int>> edges;
int n, m;

const int inf = 1e9;

void citire() {
    ifstream fin("bellmanford.in");
    fin >> n >> m;
    edges.resize(m+1);
    int p1, p2, c;

    for (int i = 1; i <= m; i++) {
        fin >> p1 >> p2 >> c;
        edges[i] = make_tuple(p1, p2, c);
    }
}

void bellmanford() {
    int dist[n+1];

    for (int i = 1; i <= n; i++) {
        dist[i] = inf;
    }
    dist[1] = 0;

    for (int i = 1; i <= n-1; i++) {
        for ( auto e: edges) {
            int p1, p2, c;
            tie(p1, p2, c) = e;
            dist[p2] = min(dist[p2], dist[p1]+c);
        }
    }

    bool neg = false;

    for (auto e : edges) {
        int p1, p2, c;
        tie(p1, p2, c) = e;

        if (dist[p1] != inf &&
            dist[p1] + c < dist[p2]) {
            neg = true;
            break;
            }
    }

    ofstream fout("bellmanford.out");

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


}

int main() {
    citire();
    bellmanford();

    return 0;
}