#include <fstream>
#define DMAX 50005
#define INFINIT 100000000
using namespace std;

ofstream fout("bellmanford.out");

struct Node
{
    int next_node;
    double cost;
};

Node ** C;

int Cmin[DMAX];
int count[DMAX];
int nrpus[DMAX];
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;

    C = new Node*[n+1];
    for(i = 1; i <= n; i++)
    {
        C[i] = new Node[n+1];
    }

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

        count[x]++;
        C[x][count[x]].next_node = y;
        C[x][count[x]].cost = c;
    }

    fin.close();
}

void BellmanFord()
{
    int inc=0, sf=-1;
    int i;
    int Q[DMAX];

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

    int x, y, c;
    optim = false;
    Cmin[1] = 0;

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

        for(i = 1; i <= count[x]; 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();
}