#include <iostream>
#include <vector>
#include <cstdio>
#include <limits.h>
#include <queue>
#define inf INT_MAX/2
using namespace std;

vector<pair<int,int> > lv[50005];
vector<pair<int,int> >::iterator ii;

queue<int> q;
int d[50005],is_in_q[50005],neg[50005];
int N,M;

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(int i=1;i<=M;i++)
    {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        lv[x].push_back(make_pair(y,c));
    }
    for(int i=2;i<=N;i++)
        d[i]=inf;
    q.push(1);
    is_in_q[1]=1;

    while(!q.empty())
    {
        int curent = q.front();
        q.pop();
        is_in_q[curent]=0;
        for(ii = lv[curent].begin(); ii!=lv[curent].end();ii++)
        {
            int nou = ii->first;
            int cost_nou = ii->second;
            if(d[nou] > d[curent] + cost_nou)
            {
                d[nou] = d[curent] + cost_nou;
                if(!is_in_q[nou]&&++neg[nou]>N)
                {
                    printf("Ciclu negativ!\n");
                    return 0;
                }
                if(!is_in_q[nou])
                {
                    q.push(nou);
                    is_in_q[nou]=1;
                }

            }
        }

    }
    for(int i=2;i<=N;i++)
        printf("%d ",neg[i]);

    return 0;
}