#include <bits/stdc++.h>
#define DIM 50005
#define oo (2<<29)

using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

struct node{
    int v,c;
    node *next;
}*L[DIM];

int N,M,d[DIM],vizitat[DIM];
bool InQueue[DIM];

void add(int x, int y, int c){
    node *p = new node;
    p->v = y, p->c = c;
    p->next = L[x];
    L[x] = p;
}

void citire(){
    f>>N>>M;
    int x,y,c;
    for(int i=1; i<=M; i++){
        f>>x>>y>>c;
        add(x,y,c);
    }
}

void BellmanFord(int Start){
    bool infinite_cicle = 0;
    queue <int> coada;
    coada.push(Start);
    InQueue[Start] = 1;
    d[Start] = 0;
    while(!coada.empty() && infinite_cicle == 0){
        int nodCurent = coada.front();
        coada.pop();
        InQueue[nodCurent] = 0;
        vizitat[nodCurent]++;
        if(vizitat[nodCurent] >= N)
            infinite_cicle = 1;
        else
            for(node *p = L[nodCurent]; p != nullptr; p = p->next)
                if(d[p->v] > d[nodCurent] + p->c)
                {
                    d[p->v] = d[nodCurent] + p->c;
                    if(InQueue[p->v] == 0){
                        InQueue[p->v] = 1;
                        coada.push(p->v);
                    }
                }
    }
    if(infinite_cicle) g<<"Ciclu negativ!";
    else
        for(int i=1; i<=N; i++)
            if(i != Start) g<<d[i]<<" ";
}

int main(){
    citire();
    for(int i=1; i<=N; i++)
        d[i] = oo;
    BellmanFord(1);
}