#include <cstdio>
#define inf 0x3f3f3f3f

using namespace std;

FILE *f=fopen("bellmanford.in","r"),*g=fopen("bellmanford.out","w");
int n,m,dist[50000],pred[50000],schimbari=true,v;
struct muchie{int a,b,c;} u[250000];

void citire()
{
    fscanf(f,"%i %i",&n,&m);
    for(int i=1;i<=m;i++)
        fscanf(f,"%i %i %i",&u[i].a,&u[i].b,&u[i].c);
}

void bellmanford()
{
    for(int i=1;i<=n;i++)
    {
        dist[i]=inf;
        pred[i]=0;
    }
    dist[1]=0;
    for(v=1;v<=n && schimbari;v++)
    {
        schimbari=false;
        for(int j=1;j<=m;j++)
        {
            if(dist[u[j].a]+u[j].c<dist[u[j].b])
            {
                dist[u[j].b]=dist[u[j].a]+u[j].c;
                schimbari++;
            }
        }
    }
}

int main()
{
    citire();
    bellmanford();
    if(v==n+1 && schimbari)
    {
        fprintf(g,"Ciclu negativ!");
        return 0;
    }
    for(int i=2;i<=n;i++)
        fprintf(g,"%i ",dist[i]);
    return 0;
}