#include <fstream>
#define INF 1000000000
using namespace std;
 
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
 
int n, start;
int cmin[8000], c[8000][8000];
int coada[8000], prim, ultim;
void citire()
{
    int i, m, x, y, cost, j;
    fin>>n>>m; start=1;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i!=j)
                c[i][j]=INF;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>cost;
        c[x][y]=cost;
    }
}
 
void bell()
{
    int i, x , ok, nr;
    int prim,ultim;
    for(i=1;i<=n;i++)
        cmin[i]=INF;
    cmin[start]=0;
    ultim=1; prim=1;
    coada[1]=start; x=start;
    while(prim<=ultim)
    {
        x=coada[prim++]; ok=0;
        for(i=1;i<=n;i++)
        {
            nr++;
            if(cmin[i]>cmin[x]+c[x][i]&&c[x][i]!=INF)
            {
                coada[++ultim]=i;
                cmin[i]=cmin[x]+c[x][i]; ok=1;
            }
        }
    }
    if(ok) fout<<"Ciclu negativ!"<<'\n';
    else
        for(i=2;i<=n;i++)
            fout<<cmin[i]<<" ";
}
int main()
{
    citire();
    bell();
    return 0;
}