#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];//graf[NMAX][NMAX],cost[NMAX];
bool oks[NMAX],oksa[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;
        }
    }
    return 0;
}

int main()
{
    f>>n>>m;
    for (int i=1;i<=n;i++)
    {
        graph[i]=new nod;
        graph[i]->ant=NULL;
        graph[i]->cost=INF;
        oks[i]=1;
    }
    graph[1]->cost=0;
    /*for (int i=2;i<=n;i++)
        cost[i]=INF:*/
    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;
        //graf[x][y]=c;
    }
    for (int aux=1;aux<n;aux++)
    {
        for (int i=1;i<=n;i++)
            if (oks[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,oksa[p->dest]=1;
                    p=p->ant;
                }
                /*for (int j=1;j<=n;j++)
                    if (graf[i][j] && cost[i]+graf[i][j]<)*/
            }
        for (int i=1;i<=n;i++)
            oks[i]=oksa[i],oksa[i]=0;
    }
    if (verifCiclu())
        g<<"Ciclu negativ!";
    else for (int i=2;i<=n;i++)
        g<<graph[i]->cost<<' ';
    g<<'\n';
    g.close();
    return 0;
}