#include <iostream>
#include <cstdio>
#include <climits>
#define NMAX 50001
#define MMAX 250005
FILE *in,*out;
using namespace std;
int cost[MMAX],vf[MMAX],urm[MMAX],lst[NMAX],q[201],nrq[NMAX],d[NMAX];
int n,m,nr,u,p,inf=INT_MAX;
bool inq[NMAX],ok;
void adauga(int x,int y,int c)
{
    nr++;
    vf[nr]=y;
    cost[nr]=c;
    urm[nr]=lst[x];
    lst[x]=nr;
}
bool bellman(int x)
{
    int poz,y,c;
    q[u++]=x;
    d[x] = 0;
    inq[x] = true;
    nrq[x] = 1;
    while(p<u)
    {
        x=q[p++];
        inq[x]=false;
        poz=lst[x];
        while(poz!=0)
        {
            y=vf[poz];
            c=cost[poz];
            if(d[x]+c<d[y])
            {
                d[y]=d[x]+c;
                if(!inq[y])
                {
                    q[u++]=y;
                    inq[y]=true;
                    nrq[y]++;
                    if(nrq[y]==n)
                        return false;
                }
            }
            poz=urm[poz];
        }
    }
    return true;
}
int main()
{
    in=fopen("bellmanford.in","r");
    out=fopen("bellmanford.out","w");
    int i,j,c;
    fscanf(in,"%d %d ", &n, &m);
    for(; m>0; m--)
    {
        fscanf(in,"%d%d%d", &i, &j,&c);
        adauga(i,j,c);
    }
    for (i = 2; i <= n; i++)
        d[i] = inf;
    if(bellman(1)==false)
        fprintf(out,"Ciclu negativ!");
    else
        for(i=2;i<=n;i++)
            fprintf(out,"%d ",d[i]);
    return 0;
}
/*
pun in coada(Q) x
cat timp Q!=0
   {scot x din Q
    inQ[x]=false
    pentru ficare y accesibil direct din x
        daca d[x]+cost(x,y)<d[y]
        {   d[y]=d[x]+cost(x,y)
            daca !inQ[y]
            { adaug y in Q
                inQ[y]=true
                nrQ[y]++
                daca nrQ[y]
                    .....ciclu negativ
            }
         }
    }
*/