#include <fstream>
#include <vector>
#include <queue>
#define NMAX 50004
#define INF 10000000
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
void citire();
bool rez;
bool BellmanFord();
void afisare();
void afisare_nrDrumMinim();
struct varf{
    int x,c;
};
vector <varf> G[NMAX];
int n,x0 = 1,m;
queue <int> C;
bool uz[NMAX];
int cmin[NMAX];
int pre[NMAX];
int nr[NMAX]; ///nr[i] - nr de drumuri de cost minim de la x0 la i
int main()
{int i;
    citire();
    rez = BellmanFord();
    afisare();
    return 0;
}
void citire()
{int i,j,c;
    fin >> n >> m;
    varf aux;
    while(fin >> i >> j >> c)
    {
        ///in lista de adiacenta a lui i trebuie sa adaug perechea (j,c)
        aux.x = j; aux.c = c;
        G[i].push_back(aux);
    }
    for (i = 1; i <= n; i++)
        cmin[i] = INF;
    cmin[x0] = 0;
    nr[x0] = 1;
}
bool BellmanFord()
{   ///returneaza 0 daca exista circuite de cost negativ si 1 altfel
    ///initializez coada cu vf de start
    int x,i,vf,cost;
    C.push(x0);
    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 afisare()
{int i,j,cnt;
    if (rez == 0) fout << "Ciclu negativ!";
    else
        for (i = 2; i <= n; i++) fout << cmin[i] << ' ';
    fout << '\n';
}
void afisare_nrDrumMinim()
{int i;
    for (i = 1; i <= n; i++)
        fout << nr[i] << " ";
    fout << '\n';
}