#include <iostream>
#include <fstream>
#define inf 999999

using namespace std;

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

int C[50000][50],d[50000],pre[50000],n,m,x,y,cost,ok;

int Bellman_Ford(){
    int i,j,k;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            for(k=1;k<=n;k++)
                if(C[j][k]!=inf && d[k]>d[j]+C[j][k]){
                    d[k]=d[j]+C[j][k];
                    pre[k]=j;
                }
    for(j=1;j<=n;j++)
        for(k=1;k<=n;k++)
            if(C[j][k]!=inf && d[k]>d[j]+C[j][k])
                return 0;
    return 1;
}

int main(){
    int i,j;
    f>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            C[i][j]=inf;
    for(i=1;i<=n;i++)
        d[i]=inf;
    for(i=1;i<=m;i++){
        f>>x>>y>>cost;
        C[x][y]=cost;
    }
    d[1]=0;
    ok=Bellman_Ford();
    if(ok==1){
    for(i=2;i<=n;i++)
        if(d[i]==inf){
            g<<"0"<<' ';

        }
        else
            g<<d[i]<<' ';
    }
    else
        g<<"Ciclu negativ";
    return 0;
}