#include <stdlib.h>
#include <stdio.h>


#define inf 999999; 

typedef struct graph {

    int nr_nodes;
    struct node ** neighbours;
} graph;

typedef struct node {

    int val;
    int cost;
    struct node* next;
} node;


void initGraph(graph *G, int n) {

    G->nr_nodes = n;

    G->neighbours = (node**)malloc((G->nr_nodes + 1) * sizeof (node*));
    for(int i = 0; i <= G->nr_nodes; i++) 
        G->neighbours[i] = NULL;
    
} 

void insertEdge (graph *G, int x, int val, int costuri) {

    node *new_node = (node*)malloc(sizeof(node));
    new_node->val = val;
    new_node->cost = costuri;
    new_node->next = G->neighbours[x];
    G->neighbours[x] = new_node;
}

int getEdge (graph G, int x, int y) {

    node *p;
    for ( p = G.neighbours[x]; p != NULL; p = p->next) 
        if(y == p->val) 
            return 1;
    return 0;
}






void Bellman_Ford(graph *G, int source, int *d) {

    for(int i = 1; i <= G->nr_nodes; i++)
        d[i] = inf;
    d[source] = 0;
    node* run;      
    for(int i = 1; i <= G->nr_nodes; i++) {
        run = G->neighbours[i];
        while (run != NULL) {

            if( d[run->val] > d[i] + run->cost)
                d[run->val] = d[i] + run->cost;
            run = run->next;
        }
    }
    for(int i = 1; i <= G->nr_nodes; i++) {
        run = G->neighbours[i];
        while (run != NULL) {

            if( d[run->val] > d[i] + run->cost) {
                printf("ciclu negativ");
                return;
            }
            run = run->next;
        }
    }
}  

int main() {


    FILE *fin;
    graph G;
    fin = fopen("bellmanford.in", "r");
    int n, m, x, y, value;
    
    fscanf(fin, "%d %d", &n, &m);
    initGraph(&G , n);

    for(int i = 0; i < m; i++) {
        fscanf(fin, "%d %d %d", &x, &y, &value);
        insertEdge(&G, x, y, value);
    }

    int *d;
    d = (int *)malloc(G.nr_nodes * sizeof(int));

    Bellman_Ford(&G,1,d);

    


    fclose(fin);
    FILE *fout;
    fout = fopen("bellmanford.out", "w");
    for(int i = 2; i <= G.nr_nodes; i++)
        fprintf(fout,"%d ", d[i]);
    fclose(fout);
    return 0;
    return 0;
}