#include <fstream>

#define INF 2<<29
#define NMAX 50001
using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

int n,m,x,y,c,dad[NMAX];

struct nod
{
    int dest,cost;
    nod *ant;
}*graph[NMAX],*p;


bool verifCiclu()
{
    for (int i=1;i<=n;i++)
    {
        p=graph[i]->ant;
        while (p)
        {
            if (graph[i]->cost+p->cost<graph[p->dest]->cost)
                return 1;
            p=p->ant;
        }
    }
}
int main()
{
    f>>n>>m;
    for (int i=1;i<=n;i++)
    {
        graph[i]=new nod;
        graph[i]->ant=NULL;
        graph[i]->cost=INF;
        dad[i]=0;
    }
    graph[1]->cost=0;
    for (int i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        p=new nod;
        p->ant=graph[x]->ant;
        graph[x]->ant=p;
        p->dest=y;
        p->cost=c;
    }
    for (int aux=1;aux<n;aux++)
        for (int i=1;i<=n;i++)
        {
            p=graph[i]->ant;
            while (p)
            {
                if (graph[i]->cost+p->cost<graph[p->dest]->cost)
                    graph[p->dest]->cost=p->cost+graph[i]->cost,dad[p->dest]=i;
                p=p->ant;
            }
        }
    if (verifCiclu())
        g<<"Ciclu negativ!";
    else for (int i=2;i<=n;i++)
        g<<graph[i]->cost<<' ';
    g<<'\n';
    g.close();
    return 0;
}