#include <vector>
#include <fstream>
#include <queue>
#define NMAX 50001
using namespace std;
ifstream fin ("bellmanford.in"); ofstream fout ("bellmanford.out");
int n, m, st, cmin[NMAX], prec[NMAX], inf=1000000000;
int nr[NMAX];
bool ciclic=0;

struct arc {int vf, c;};

vector <arc> G[NMAX];
queue <int> C;

void citire()
{   arc crt;
    int i, x;
    fin>>n>>m; st=1;
    for (i=0; i<m; i++)
        {
            fin>>x>>crt.vf>>crt.c;
            //arcul curent intra in lista de adiacenta a lui x
            G[x].push_back(crt);
        }
}

void initializare()
{
    int i;
     for (i=1; i<=n; i++) cmin[i]=inf, prec[i]=st;
     prec[st]=0; cmin[st]=0;
     //parcurg lista de adiacenta a lui st si completez in cmin costurile arcelor
     for (i=0; i<G[st].size(); i++)
         cmin[G[st][i].vf]=G[st][i].c;
     //si coada
     for (i=0; i < n; i++) C.push(i);

}


void rec (int i) {
    if (i!=st) rec(prec[i]);
    fout<<i<<' ';
}
int main()
{
    int i, vf, aux;
    citire();
    initializare();
    while (!C.empty() && !ciclic) {
        vf=C.front(); C.pop();
        for (i=0; i<G[vf].size() && !ciclic; ++i) {
            aux=cmin[vf]+G[vf][i].c;
            if (aux<cmin[G[vf][i].vf]) {
                cmin[G[vf][i].vf]=aux;
                prec[G[vf][i].vf]=vf;
                C.push(G[vf][i].vf);
                ++nr[G[vf][i].vf];
                if (nr[G[vf][i].vf]>=n) ciclic=1;
            }
        }
    }
    if (ciclic) fout<<"Ciclu negativ!\n";
    else {
        for (i=2; i<=n; ++i) fout<<cmin[i]<<' ';
        fout<<'\n';
    }
    return 0;
}