#include <stdio.h>
#include <stdlib.h>
#define INF 99999999
typedef struct pereche
{
    int start,stop,cost;
} pereche;
typedef struct node
{
    int val,cost;
    struct node* next;
} node;
typedef struct graph
{
    int nr_nodes;
    struct node** neighbours;
} graph;
graph * initG(int n)
{
    int i;
    graph *G;
    G=malloc(sizeof(graph));
    G->nr_nodes=n;
    G->neighbours=calloc(n+1,sizeof(node));
    for(i=0;i<n;i++)
        G->neighbours[i]=NULL;
    return G;
}
node * initN(int n)
{
    node *nou;
    nou=(node*)malloc(sizeof(node));
    nou->val=n;
    nou->next=NULL;
    return nou;
}
FILE *input,*output;
pereche E[250000];
int d[50000],cnt[50000];
void BellmanFord(graph *G,int source)
{
    int i;
    for(i=1;i<=G->nr_nodes;i++)
        {
        d[i]=INF;
        cnt[i]=0;
        }
    d[source]=0;
    for(i=1;i<G->nr_nodes;i++)
        for(i=1;i<=E[0].start;i++)
            if(d[E[i].stop]>d[E[i].start]+E[i].cost)
            d[E[i].stop]=d[E[i].start]+E[i].cost;
    for(i=1;i<=E[0].start;i++)
        if(d[E[i].stop]>d[E[i].start]+E[i].cost)
            {
            fprintf(output,"Ciclu negativ!\n");
            return;
            }
    for(i=2;i<=G->nr_nodes;i++)
        //printf("Costul drumului de la nodul %d la nodul %d este %d.\n",source,i,d[i]);
        fprintf(output,"%d ",d[i]);
}
int main()
{
    int i,n,m,start,stop,pret,source;
    graph *G;
    node *nou;
    input=fopen("bellmanford.in","r");
    output=fopen("bellmanford.out","w");
    fscanf(input,"%d%d",&n,&m);
    G=initG(n);
    E[0].start=m;
    for(i=1;i<=m;i++)
    {
        fscanf(input,"%d%d%d",&start,&stop,&pret);
        nou=initN(stop);
        E[i].start=start;
        E[i].stop=stop;
        E[i].cost=pret;
        nou->next=G->neighbours[start];
        nou->cost=pret;
        //cost[start][stop]=pret;
        G->neighbours[start]=nou;
    }
    BellmanFord(G,1);
    return 0;
}