//
//  main.cpp
//  Bellman-Ford infoarena
//
//  Created by Razvan Vranceanu on 07/02/2020.
//  Copyright © 2020 Razvan Vranceanu. All rights reserved.
//

#include <fstream>
#define N 50001
#define inf 200000000
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

int n, m, q[N], contor[N], d[N];
bool viz[N];
struct Nod{
    int nod, cost;
    Nod *leg;
} *L[N];
void adauga(Nod *&pp, int val, int cost)
{
    Nod *p = new Nod;
    p->nod=val;
    p->cost=cost;
    p->leg=pp;
    pp=p;
}
void citire()
{
    f>>n>>m;
    for(int i=2;i<=m;i++)
    {
        int x,y,cost;
        f>>x>>y>>cost;
        adauga(L[x], y, cost);
    }
}
void BellmanFord()
{
    bool areCN = 0;
    int i, pr, ul, k,c;
    Nod *p;
    pr=ul=1;
    for(int i=2;i<=n;i++) d[i]=inf;
    d[1]=0;
    viz[1]=1;
    q[ul]=1;
    while(pr<=ul && !areCN)
    {
        //extrage un nod k din coada
        k=q[pr++];
        viz[k]=0; //
        for(p=L[k]; p; p=p->leg)
        {
            i=p->nod;
            c=p->cost;
            if(d[i] > c + d[k])
            {
                d[i] = c + d[k];
                if(!viz[i])
                {
                    if(contor[i] > n)
                        areCN = 1;
                    else{
                        q[++ul]=i;
                        viz[i]=1;
                        contor[i]++;
                    }
                }
                
            }
        }
    }
    //afisare
    if(!areCN)
    {
        for(int i=2;i<=n;i++)
            g<<d[i]<<" ";
    }
    else g<<"Ciclu negativ!\n";
}

int main()
{
    citire();
    BellmanFord();
    return 0;
}