#include<fstream>
#include<vector>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int vc[50001];
int inf=1<<30;
struct ad{
    int nda,vl;
};
vector<ad>q[50001];
int main(){
    int n,m,i,a,b,c,j,k;
    fin>>n>>m;
    ad aux;
    bool ok;
    for(i=1;i<=n;i++)
        vc[i]=inf;
    vc[1]=0;
    for(i=1;i<=m;i++){
        fin>>a>>b>>c;
        aux.nda=b;
        aux.vl=c;
        q[a].push_back(aux);
    }
    for(k=1;k<=m&&!ok;k++){
        ok=true;
    for(i=1;i<=n;i++){
        if(vc[i]!=inf)
        for(j=0;j<q[i].size();j++){
            aux=q[i][j];
            if(vc[aux.nda]>vc[i]+aux.vl){
                vc[aux.nda]=vc[i]+aux.vl;ok=false;
                }
        }
    }
    }
    if(!ok)fout<<"Ciclu negativ!"<<'\n';
    else{
        for(i=2;i<=n;i++)
            fout<<vc[i]<<" ";
        fout<<'\n';
    }
    fin.close();
    fout.close();
    return 0;
}