#include<stdio.h>
#define maxn 50000
#define maxm 250000
#define INF 1001
struct muchie
{
    int a;
    int b;
    int cost;
}EDGE[maxm];
int n,m,i,j,dist[maxn];
void BellmanFord()
{
    int i,j;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(dist[EDGE[j].a] + EDGE[j].cost < dist[EDGE[j].b])
                dist[EDGE[j].b]=dist[EDGE[j].a] + EDGE[j].cost;
}
int verif_negativ()
{
    int i;
    for(i=1;i<=m;i++)
        if(dist[EDGE[i].a] + EDGE[i].cost < dist[EDGE[i].b])
            return 1;
    return 0;
}
int main()
{
    FILE *f=fopen("bellmanford.in","rt");
    FILE *g=fopen("bellmanford.out","wt");
    fscanf(f,"%i%i",&n,&m);
    for(i=1;i<=n;i++)
        fscanf(f,"%i%i%i",&EDGE[i].a,&EDGE[i].b,&EDGE[i].cost);
    dist[1]=0;
    for(i=2;i<=n;i++)
        dist[i]=INF;
    BellmanFord();
    if(verif_negativ())
        fprintf(g,"Ciclu negativ!\n");
    for(i=2;i<=n;i++)
        fprintf(g,"%i ",dist[i]);
    return 0;
}