#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define NRMAX 50005
#define INF 100000
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

struct graf{int vf,c;};
int n,m;

queue <int> C;
vector <graf> L[NRMAX];
int cmin[NRMAX];
int pred[NRMAX];
int nr[NRMAX];
vector <bool> uz(NRMAX,0);

void citire();
void BLMF();
void afisare();
int main()
{
citire();
BLMF();
    return 0;
}

void citire()
{
    int i,v1,v2,c;

    fin>>n>>m;
    for(i=1;i<=m;i++)
        {fin>>v1>>v2>>c;
         L[v1].push_back({v2,c});
        }

for(i=1;i<=n;i++)
    {cmin[i]=INF;
     pred[i]=1;
    }
for(i=0;i<L[1].size();i++)
    cmin[L[1][i].vf]=L[1][i].c;
cmin[1]=0;pred[1]=0;
uz[1]=1;
C.push(1);
}

void BLMF()
{
    int x,i;
    bool ok=1;

    while(!C.empty() && ok)
    {
     x=C.front();C.pop();

     for(i=0;i<L[x].size();i++)
         {
          if(cmin[L[x][i].vf] > cmin[x] + L[x][i].c)
            {
              cmin[L[x][i].vf]=cmin[x] + L[x][i].c;
              pred[L[x][i].vf]=x;
              nr[L[x][i].vf]++;

            }
         if(nr[L[x][i].vf]==n)
                {ok=0;break;}
                else
            if(uz[L[x][i].vf]==0)
             {C.push(L[x][i].vf);
             uz[L[x][i].vf]=1;
             }
         }
    }


if(ok==0)
    fout<<"Ciclu negativ!"<<'\n';
else
    afisare();
}

void afisare()
{
    int i;

    for(i=2;i<=n;i++)
        fout<<cmin[i]<<' ';
    fout<<'\n';
}