#include <fstream>
#include <vector>
#include <queue>
#define NRMAX 50001
#define INF 1000000

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

struct graf{
    int y, c;
};

int n, m;
bool ok = 1;

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

void citire();
void bf();
void afisare();

int main()
{
    citire();
    bf();
    afisare();
    return 0;
}

void citire()
{
    int i, x, z, c;
    fin >> n >> m;
    for(i = 1; i <= m; i++)
    {
        fin >> x >> z >> c;
        L[x].push_back({z,c});
    }
}
void bf()
{
    int x,i;
    for(i = 1; i <= n; i++)
    {
        cmin[i] = INF;
        pred[i] = 0;
    }
    cmin[1] = 0;
    uz[1] = 1;
    nr[1]++;
    C.push(1);
    while(C.empty() == 0)
    {
        x = C.front();
        C.pop();
        uz[x] = 0;
        for(i = 0; i < L[x].size(); i++)
        {
            if(cmin[L[x][i].y] > cmin[x] + L[x][i].c)
            {
                cmin[L[x][i].y] = cmin[x] + L[x][i].c;
                pred[L[x][i].y] = x;
                nr[L[x][i].y]++;
                if(uz[L[x][i].y] == 0)
                {
                    C.push(L[x][i].y);
                    uz[L[x][i].y] = 1;
                    if(nr[L[x][i].y] > n)
                    {
                        ok = 0;
                        break;
                    }
                }
            }
         }
         if (ok == 0)
            break;
    }
}

void afisare()
{
    int i;
    if(ok == 0)
        fout << "Ciclu negativ!";
    else
    {
        for(i = 2; i <= n; i++)
            fout << cmin[i] <<' ';
    }
}