#include <cstdio>
#include <vector>
using namespace std;
#define NMAX 50005
#define MMAX 250005
#define INFINIT 1000000000

struct EDGE{
    int x, y, cost;
};

int main(){

    bool cicluNeg = false;
    EDGE temp;
    vector<EDGE> edges;
    int n, m, d[NMAX];
    int a, b, c, i, j;
    FILE *fin, *fout;
    fin = fopen("bellmanford.in", "r");
    fout = fopen("bellmanford.out", "w");

    fscanf(fin, "%d %d", &n, &m);
    for(i=1; i<=m; i++){
        fscanf(fin, "%d %d %d", &a, &b, &c);
        temp.x = a;
        temp.y = b;
        temp.cost = c;
        edges.push_back(temp);
    }

    for(i=2; i<=n; i++)
        d[i] = INFINIT;
    d[1] = 0;

    for(i=1; i<=n-1; i++){
        for(j=0; j<m; j++){
            if(d[ edges[j].y ] != INFINIT || d[ edges[j].x ] != INFINIT){
                if(d[ edges[j].y ] > d[ edges[j].x ] + edges[j].cost){
                    d[ edges[j].y ] = d[ edges[j].x ] + edges[j].cost;
                }
            }
        }
    }

    for(j=0; j<m; j++){
            if(d[ edges[j].y ] != INFINIT || d[ edges[j].x ] != INFINIT){
                if(d[ edges[j].y ] > d[ edges[j].x ] + edges[j].cost){
                    cicluNeg = true;
                    break;
                }
            }
        }

    if(cicluNeg)
        fprintf(fout, "Ciclu negativ!\n");

    for(i=2; i<=n; i++)
        fprintf(fout, "%d ", d[i]);

    return 0;
}