#include <fstream>
#define inf 9999999
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int a[250001],b[250001],c[250001],n,m,cost[50001];
void cit(){
    int i;
    fin>>n>>m;
    for(i=2;i<=n;i++)
        cost[i]=inf;
    for(i=1;i<=m;i++)
        fin>>a[i]>>b[i]>>c[i];
    fin.close();
}
void rez(){
    int i,j;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(cost[a[j]]+c[j]<cost[b[j]])
                cost[b[j]]=cost[a[j]]+c[j];
}
int verif(){
    int i;
    for(i=1;i<=m;i++)
        if(cost[a[i]]+c[i]<cost[b[i]])
            return 1;
    return 0;
}
int main(){
    cit();
    rez();
    if(verif())
         fout<<"Ciclu negativ!";
    else{
        for(int i=2;i<=n;i++)
            fout<<cost[i]<<" ";
    }
    fout.close();
    return 0;
}