#include<fstream>
#define INF 10000000
using namespace std;
ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");
int mat[20001][20001],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(j=1;j<=n;j++){
                if(mat[i][j]!=INF && d[j]>d[i]+mat[i][j])
                    d[j]=d[i]+mat[i][j];
            }
        }
    }
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            if(mat[i][j]!=INF && d[j]>d[i]+mat[i][j])
                return 0;
        }
    }
    return 1;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            mat[i][j]=INF;
        }
    }
    for(int i=1;i<=m;i++){
        cin>>a>>b>>cost;
        mat[a][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;
}