#include <bits/stdc++.h>
#define Nmax 50005
#define oo 0x3f3f3f3f
using namespace std;

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

int N, M;
int Viz[Nmax], D[Nmax];
bool InCoada[Nmax];
vector < pair <int,int> > G[Nmax];
queue <int> Coada;

void Citire()
{
    int x, y, c;
    fin >> N >> M;
    for (int i=1; i<=N; i++)
    {
        fin >> x >> y >> c;
        G[x].push_back(make_pair(c,y));
    }
}
bool BellmanFord(int NodStart)
{
    for (int i=1; i<=N; i++)
        D[i] = oo;
    D[NodStart] = 0;
    Viz[NodStart]++;
    InCoada[NodStart] = true;
    Coada.push(NodStart);
    while (!Coada.empty())
    {
        int NodCurent = Coada.front();
        Viz[NodCurent]++;
        if (Viz[NodCurent]>N)
            return false;
        InCoada[NodCurent] = false;
        Coada.pop();
        for (size_t i=0; i<G[NodCurent].size(); i++)
        {
            int Cost = G[NodCurent][i].first;
            int Vecin = G[NodCurent][i].second;
            if (D[Vecin] > Cost + D[NodCurent])
            {
                D[Vecin] = Cost + D[NodCurent];
                if (InCoada[Vecin] == false)
                {
                    Coada.push(Vecin);
                    InCoada[Vecin] = true;
                }
            }
        }
    }
    return true;
}
int main()
{
    Citire();
    if (BellmanFord(1))
    {
        for (int i=2; i<=N; i++)
            fout << D[i] << " ";
    }
    else
        fout << "Ciclu negativ!";

}