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

typedef pair<int, int> ii;
vector<ii> a[NMAX];
int n, m, source, d[NMAX];

void BlmnFord(){
    int i, j, x=1;
    ii nod;
    while(x <= n-1){
        for(i=1; i<=n; i++){
            for(j=0; j<(int) a[i].size(); j++){
                nod = a[i][j];
                if(d[ nod.first ] > d[ i ] + nod.second){
                    d[ nod.first ] = d[ i ] + nod.second;
                }
            }
        }
        x++;
    }
}

bool negCicle(){
    int i, j;
    ii nod;
    for(i=1; i<=n; i++){
            for(j=0; j<(int) a[i].size(); j++){
                nod = a[i][j];
                if(d[ nod.first ] > d[ i ] + nod.second){
                    return true;
                }
            }
        }

    return false;
}

int main(){

    int i, j, x, y, c;
    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", &x, &y, &c);
        a[x].push_back(ii(y, c));
    }

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

    BlmnFord();

    if(negCicle())
        fprintf(fout, "Ciclu negativ!\n");
    for(i=2; i<=n; i++)
        fprintf(fout, "%d ", d[i]);

    return 0;
}