#include <fstream>
#include <vector>
#include <queue>
#define inf 1 << 30
#define nmax 50000+5

using namespace std;

struct muchie
{
    int dest;
    int dist;
    muchie(int dest, int dist): dest(dest), dist(dist)
    {

    }
};

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

vector<muchie> graf[nmax];
queue<int> coada;
int apartineCoada[nmax];
int nrVerificat[nmax];
int cost[nmax];
int n;

void citire()
{
    int i, m;
    int x, y, c;

    fin >> n >> m;
    for (i = 1; i <= m; i++)
    {
        fin >> x >> y >> c;
        graf[x].push_back(muchie(y, c));
    }
}

void bellmanFord()
{
    int i;
    int curent;
    int ciclu_negativ;
    int tentativ;
    vector<muchie>::iterator vecin;

    for (i = 1; i <= n; i++)
    {
        cost[i] = inf;
        apartineCoada[i] = nrVerificat[i] = 0;
    }

    coada.push(1);
    cost[1] = 0;
    apartineCoada[1] = 1;
    nrVerificat[1] = 0;
    ciclu_negativ = 0;

    nrVerificat[1];
    while (!coada.empty() && !ciclu_negativ)
    {
        curent = coada.front();
        coada.pop();

        for (vecin = graf[curent].begin(); vecin != graf[curent].end(); vecin++)
        {
            tentativ = cost[curent] + (*vecin).dist;
            if (tentativ < cost[(*vecin).dest])
            {
                cost[(*vecin).dest] = tentativ;
                nrVerificat[(*vecin).dest]++;
                if (nrVerificat[(*vecin).dest] > n)
                {
                    ciclu_negativ = 1;
                    break;
                }
                if (!apartineCoada[(*vecin).dest])
                {
                    apartineCoada[(*vecin).dest] = 1;
                    coada.push((*vecin).dest);
                }
            }
        }

        apartineCoada[curent] = 0;
    }

    if (ciclu_negativ)
        fout << "Ciclu negativ!";
    else for (i = 2; i <= n; i++)
        fout << cost[i] << ' ';
    fout << '\n';
}

int main()
{
    citire();
    bellmanFord();
}