#include<fstream>
//#include<iostream>
#include<vector>
#define INF 10000000
using namespace std;
ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");
struct muchie{
    int y;
    int cost;
};
vector<muchie>mat[50005];
int a,b,cost,d[50001],n,m;
bool bellman_ford(){
    int i,j,k;
    for(k=1;k<=n;k++){
        for(i=1;i<=n;i++){
            for(int j=0;j<mat[i].size();j++){
                if(d[mat[i][j].y]>d[i]+mat[i][j].cost)
                    d[mat[i][j].y]=d[i]+mat[i][j].cost;
            }
        }
    }
    for(i=1;i<=n;i++){
        for(int j=0;j<mat[i].size();j++){
            if(d[mat[i][j].y]>d[i]+mat[i][j].cost)
                return 0;
        }
    }
    return 1;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a>>b>>cost;
        mat[a].push_back({b,cost});
    }
    for(int j=1;j<=n;j++)
        d[j]=INF;
    d[1]=0;
    if(!bellman_ford())
        cout<<"Ciclu negativ!";
    else{
        for(int j=2;j<=n;j++)
            cout<<d[j]<<" ";
    }
    return 0;
}