#include <fstream>
#include <vector>

using namespace std;

ifstream cin ( "bellmanford.in" );
ofstream cout ( "bellmanford.out" );

#define NMAX 50000
#define INF ( 1 << 30 )

struct graph {
    int node, cost;
};

int dist[NMAX + 1];
vector<graph> G[NMAX + 1];

void bellman_ford( int n, int m, int source ) {
    int i;
    for ( i = 1; i <= n; i++ ) {
        dist[i] = INF;
    }
    dist[source] = 0;
    for ( i = 1; i <= n - 1; i++ ) {
        for ( graph copil : G[i] ) {
            if ( dist[i] + copil.cost < dist[copil.node] ) {
                dist[copil.node] = dist[i] + copil.cost;
            }
        }
    }
    for ( graph copil : G[i] ) {
        if ( dist[i] + copil.cost < dist[copil.node] ) {
            cout << "Ciclu negativ!";
            return;
        }
    }
    for ( i = 2; i <= n; i++ ) {
        cout << dist[i] << " ";
    }
}

int main() {
    int n, m, i, a, b, c;
    cin >> n >> m;
    for ( i = 1; i <= m; i++ ) {
        cin >> a >> b >> c;
        G[a].push_back({b, c});
    }
    bellman_ford(n, m, 1);
    return 0;
}