#include <iostream>
#include <stdio.h>
#include <queue>
#include <vector>
#include <bitset>
using namespace std;

#define NMAX 50005
struct nod
{
    int c,y;
};

vector <nod> g[NMAX];
queue <nod> q;
int d[NMAX];
int cont[50005];

int functie(int m, int n)
{
    nod x;
    bitset <50005> v;
    v=0;
    int i=1;
    x.y=m;
    x.c=0;
    q.push(x);
    int s;

    while(!(q.empty()))
   {
        s=q.front().y;
        v[s]=0;
        q.pop();

        for(int j=0; j<g[s].size(); j++)
        {
            if(d[g[s][j].y]>d[s]+g[s][j].c)
           {
               if(++cont[s]==n)
                    return 0;

               x.y=g[s][j].y;
               x.c=d[s]+g[s][j].c;

               if(v[x.y]==0)
               {
                   q.push(x);
                   v[x.y]=1;
               }
               d[g[s][j].y]=d[s]+g[s][j].c;
           }
        }
   }
   return 1;
}

int main()
{
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);

    int n, m, a, b, c;
    nod x;
    scanf("%d %d \n", &n, &m);
    for(int i=1; i<=m; i++)
    {
        scanf("%d %d %d \n", &a,&b,&c);
        x.y=b;
        x.c=c;
        g[a].push_back(x);
    }

    for(int i=2; i<=n; i++) d[i]=NMAX*100;
    if(functie(1,n)==0)
        cout<<"Ciclu negativ!";
    else
    {
        for(int i=2; i<=n; i++)
            cout<<d[i]<<" ";
    }




    return 0;
}