#include<cstdio>
#define maxn 50003
#include<queue>
#include<vector>
#define inf 9999999
using namespace std;
vector <int > C[maxn],G[maxn];
int d[maxn],nr[maxn],n,m,x,y,c;
queue <int> Q;
int Bell(){
    for(int i=2;i<=n;++i)
        d[i]=inf;
    d[1]=0;
    nr[1]=1;
    Q.push(1);
    while(!Q.empty()){
        int x=Q.front(); Q.pop();
        for(int i=0;i<G[x].size();++i){
            int p=G[x][i];
            if(d[p]>C[x][i]+d[x]){
                d[p]=C[x][i]+d[x];

            }
            if(nr[p]==n){
                return 0;
            }
            else
                if(nr[p]==0){
                    Q.push(p);
                    ++nr[p];
                }
                else
                    nr[p]++;
        }
    }
    return 1;
}
int main(){
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d%d%d", &x, &y, &c);
        C[x].push_back(c);
        G[x].push_back(y);
    }
    if(Bell())
        for(int i=2;i<=n;++i)
            printf("%d ",d[i]);
    else
        printf("Ciclu negativ!");
    return 0;
}