#include<fstream>
#include<queue>
#include<iostream>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
struct qwerty{
    bool ok;
    int weight;
}x[55555][55555];
int s=0,S=0;
queue<int>q;
int z[111],i,j,n,m,a,b;
bool v[111];
int pr1(){
    while(!q.empty()){
        if(z[a]<S)
            return 1;
        for(i=2;i<=n;i++)
            cout<<z[i]<<' ';
        cout<<'\n';
        a=q.front();
        q.pop();
        v[a]=false;
        for(i=2;i<=n;i++)
            if(x[a][i].ok){
                if(z[i]>z[a]+x[a][i].weight)
                    z[i]=z[a]+x[a][i].weight;
                    if(v[i]==false){
                        q.push(i);
                        v[i]=true;
                    }
            }
    }
    return 2;
}
int main(){
    z[1]=0;
    v[1]=true;
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>a>>b,
        fin>>x[a][b].weight,
        x[a][b].ok=true;
        if(x[a][b].weight>0)
            s+=x[a][b].weight;
        else
            S+=x[a][b].weight;
    }
    for(i=2;i<=n;i++)
        z[i]=s*2;
    q.push(1);
    int aa=pr1();
    if(aa==2)
        for(i=2;i<=n;i++)
            fout<<z[i]<<' ';
    else
        fout<<"Ciclu negativ!";
    return 0;
}