#include <cstdio>
#include <list>
using namespace std;

struct edge{

    int u, v;
    int weight;

    edge(int _u, int _v, int _w){
        u = _u;
        v = _v;
        weight = _w;
    }
};

int vertices, edges, u, v, weight;
int dist[50001], predecessor[50001];
list<edge> adj[50001];
const int infinity = 250000001;

int BellmanFord(int source){

    for(int node = 1; node <= vertices; node++){
        dist[node] = infinity;
        predecessor[node] = NULL;
    }dist[source] = 0;

    for(int i = 1; i <= vertices - 1; i++){
        for(int node = 1; node <= vertices; node++){
            for(list<edge>::iterator it = adj[node].begin(); it != adj[node].end(); it++){

                int u = it -> u;
                int v = it -> v;
                int weight = it -> weight;

                if(dist[u] + weight < dist[v]){
                    dist[v] = dist[u] + weight;
                    predecessor[v] = u;
                }
            }
        }
    }
    for(int node = 1; node <= vertices; node++){
        for(list<edge>::iterator it = adj[node].begin(); it != adj[node].end(); it++){

            int u = it -> u;
            int v = it -> v;
            int weight = it -> weight;

            if(dist[u] + weight < dist[v]){
                return 0;
            }
        }
    }
    return 1;
}

int main(){

    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);

    scanf("%d %d", &vertices, &edges);

    for(int i = 1; i <= edges; i++){
        scanf("%d %d %d", &u, &v, &weight);
        adj[u].push_back(edge(u, v, weight));
    }
    if(BellmanFord(1) == 0){
        printf("Ciclu negativ!");
        return 0;
    }
    for(int node = 2; node <= vertices; node++){
        printf("%d ", dist[node]);
    }
    return 0;
}