#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];
int isLnr;
//int graf[NMAX][NMAX],cost[NMAX];

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

/*
struct nod1
{
    int info;
    nod1 *urm;
}*l[2],*q;
*/
int coada[2][NMAX],dr[2],NRC;

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;
        coada[0][i]=i;
    }
    dr[0]=n;
    graph[1]->cost=0;
    /*
    for (int i=2;i<=n;i++)
        cost[i]=INF,oksa[i]=1:
    */
    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]!=oksa[i])
        */
        int i;
            for (int st=1;st<=dr[NRC];st++)
            {
                //oks[i]=oksa[i];
                i=coada[NRC][st];
                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,coada[1-NRC][++dr[1-NRC]]=p->dest;//oksa[p->dest]++;
                    p=p->ant;
                }
                /*
                for (int j=1;j<=n;j++)
                    if (graf[i][j] && cost[i]+graf[i][j]<cost[j])
                    {
                        cost[j]=cost[i]+graf[i][j];
                        oksa[i]=1;
                    }
                */
            }
        dr[NRC]=0;
        NRC=1-NRC;
    }
    if (verifCiclu())
        g<<"Ciclu negativ!";
    else for (int i=2;i<=n;i++)
        g<<graph[i]->cost<<' ';
    g<<'\n';
    g.close();
    return 0;
}