#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

struct dt
{
    int catre,cost;
};
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

vector<dt> lista[50001];
queue<int> coada;
int viz[50001],n,m,drum[50001],x,y,c;
bool InCoada[50001];

void BF()
{
    coada.push(1);
    InCoada[1] = 1;
    int nod,cost,vecin;
    while(!coada.empty())
    {
        nod = coada.front();
        InCoada[nod] = 0;
        coada.pop();
        if(viz[nod] == n)
        {
            g<<"Ciclu negativ!";
            return;
        }

        for(int i = 0;i<lista[nod].size();i++)
        {
            cost = lista[nod][i].cost;
            vecin = lista[nod][i].catre;

            if(drum[vecin] > drum[nod]+cost)
            {
                drum[vecin] = drum[nod]+cost;
                viz[vecin]++;
                if(InCoada[vecin] == 0)
                {
                    coada.push(vecin);
                    InCoada[vecin] = 1;
                }
            }

        }
    }

    for(int i = 2;i<=n;i++)
        g<<drum[i]<<' ';

}


int main()
{

    f>>n>>m;

    for(int i = 2;i<=n;i++)
        drum[i] = 999999999;

    dt aux;
    for(int i = 1;i<=m;i++)
    {
        f>>x>>y>>c;
        aux.catre = y;aux.cost=c;
        lista[x].push_back( aux);
    }
    BF();


    f.close();
    g.close();

    return 0;
}