#include <iostream>
#include <cstring>
#include<cstdio>
#include <queue>
#include <vector>
#define inf 0x3f3f3f3f
using namespace std;
vector <pair<int,int> > lv[50009];
queue <int> q;
vector <pair<int,int> > ::iterator ii;
int d[50009],n,m,a,b,c,nr[50009];
int main()
{
    int nc;
     FILE *f=fopen("bellmanford.in","r");
     FILE *f1=fopen("bellmanford.out","w");
    fscanf(f,"%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
         fscanf(f,"%d%d%d",&a,&b,&c);
         lv[a].push_back(make_pair(b,c));
    }
    memset(d,inf,sizeof(d));
    q.push(1);
    d[1]=0;
    while(!q.empty())
    {
        nc=q.front();
        q.pop();
        for(ii=lv[nc].begin();ii!=lv[nc].end();++ii)
            if(d[ii->first]>d[nc]+ii->second)
        {
            d[ii->first]=d[nc]+ii->second;
            q.push(ii->first);
            ++nr[ii->first];
            if(nr[ii->first]>=n)
            {
                fprintf(f1,"Ciclu negativ!\n");
                return 0;
            }

        }

    }

      for(int i = 2; i <= n; ++i)
        fprintf(f1,"%d ", d[i]);
    return 0;
}