#include <fstream>
#include <vector>
#define INF 1e9
#include <queue>
using namespace std;

ifstream cin ("bellmanford.in");
ofstream cout ("bellmanford.out");

struct varf
{
    int x, c;
};

int n, m, x0=1, rez;

vector <varf> G[102]; ///liste de adiacenta cu costuri

bool uz[50002];
int cmin[50002];
int pre[50002];
int nr[50002]; //nr de drumuri de cost minim de la x0 la i

queue <int> C;

void citire();
bool bf();
void afis();

int main()
{
    citire();
    rez=bf();
    afis();
    return 0;
}


void citire()
{
    int i, j, c;
    varf aux;
    cin>>n>>m;
    while (cin>>i>>j>>c)
    {
        //in lista de adiacenta a lui i trebuie sa adaug perechea j,k
        aux.x=j;
        aux.c=c;
        G[i].push_back(aux);
    }

    for (i=1; i<=n; i++)
        cmin[i]=INF;
    cmin[x0]=0;


}

bool bf()
{
    ///returneaza 0 daca exista circuite de cost negativ si 1 altfel

    ///initializez coada cu vf de start

    int i, vf, cost, x;
    C.push(x0);
     nr[x0]=1;
     while (!C.empty())
     {
         x=C.front();
         C.pop();
         ///parcurg lista de adiacenta a lui x
         for (i=0; i<G[x].size(); i++)
         {
             vf=G[x][i].x;
             cost=G[x][i].c;
             if (cmin[vf]>cmin[x]+cost)
             {
                 cmin[vf]=cmin[x]+cost;
                 C.push(vf);
                 nr[vf]++;
                 if (nr[vf]==n)
                    return 0;
             }
         }
     }
     return 1;
}

void afis()
{
    int i, j, cnt;
   if (rez==0)
    cout<<"Ciclu negativ!";
   else
    for (i=2; i<=n; i++)
   cout<<cmin[i]<<' ';
   cout<<'\n';

}