#include <stdio.h>
#include <string>
#include <queue>
#include <bitset>
using namespace std;
#define INF 0x3f3f3f3f
#define nmax 50001
#define mmax 250001
#define pb push_back
vector<int> v[nmax],c[nmax];
queue<int> q;
int n,m,x,y,z,i,j,nod;
int d[nmax],iq[nmax],mark[mmax];
int main()
{
    freopen ("bellmanford.in","r",stdin);
    freopen ("bellmanford.out","w",stdout);
    scanf ("%d %d",&n,&m);
    for (i=1;i<=m;++i){
        scanf ("%d %d %d",&x,&y,&z);
        v[x].pb(y);
        c[x].pb(z);
        }
    memset(d,INF,sizeof(d));
    d[1]=0;
    q.push(1);
    iq[1]=1;
    while (!q.empty()){
          nod=q.front();
          iq[nod]=0;
          q.pop();
          for (i=0;i<v[nod].size();++i){
              if (d[nod]+c[nod][i]<d[v[nod][i]]){
                 d[v[nod][i]]=d[nod]+c[nod][i];
                 if (!iq[v[nod][i]]){
                    q.push(v[nod][i]);
                    iq[v[nod][i]]=1;
                    mark[v[nod][i]]++;
                    if (mark[v[nod][i]]>=n){
                       printf("Ciclu negativ!\n");
                       return 0;
                       }
                    }
                 }
              }
          }
    for (i=2;i<=n;++i)
        printf("%d ",d[i]);
    printf("\n");
    return 0;
}