#include <fstream>
#include <vector>
#define DMAX 50010
#define INFINIT 250000000
using namespace std;

ofstream fout("bellmanford.out");

struct Node
{
    int next_node;
    int cost;
    Node(int a, int b):next_node(a), cost(b) { }
};

vector <Node> C[DMAX];

int Cmin[DMAX], nrpus[DMAX], Q[500000];;
int n, m;
bool optim;

void citire();
void BellmanFord();
void afisare();

int main()
{
    citire();
    BellmanFord();
    afisare();
    fout.close();
    return 0;
}

void citire()
{
    ifstream fin("bellmanford.in");
    int i,x,y,c;

    fin >> n >> m;

    for(i = 1; i <= m; i++)
    {
        fin >> x >> y >> c;

        C[x].push_back(Node(y,c));
    }

    fin.close();
}

void BellmanFord()
{
    int inc=0, sf=-1;
    int i;

    for(i = 1; i<= n; i++)
    {
        Q[++sf] = i; nrpus[i]++;
        Cmin[i] = INFINIT;
    }
    Cmin[1] = 0;

    int x, y, c;
    optim = false;

    while(inc <= sf)
    {
        x = Q[inc++];

        for(i = 0; i < C[x].size(); i++)
        {
            y = C[x][i].next_node;
            c = C[x][i].cost;

            if(Cmin[x] + c < Cmin[y])
            {
                Cmin[y] = Cmin[x]+c;
                Q[++sf] = y;
                nrpus[y]++;
                if(nrpus[y] >= n)
                {
                    optim = true;
                    sf = -1;
                    break;
                }
            }
        }
    }
}

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

    fout.close();
}