BEGIN

  d(v[1]) ← 0

  FOR j = 2,..,n DO

    d(v[j]) ← ∞

  FOR i = 1,..,(|V|-1) DO

    FOR ALL (u,v) in E DO

      d(v) ← min(d(v), d(u)+l(u,v))

  FOR ALL (u,v) in E DO

    IF d(v) > d(u) + l(u,v) DO

      Message: "Negative Circle"

END

#include <stdio.h>
#include <limits.h>

#define MAX_VERTICES 100
#define MAX_EDGES 100

typedef struct {
    int u, v, weight;
} Edge;

int numVertices, numEdges;
int distance[MAX_VERTICES];
Edge edges[MAX_EDGES];

void bellmanFord(int startVertex) {
    distance[startVertex] = 0;

    for (int j = 1; j <= numVertices; j++) {
        if (j != startVertex) {
            distance[j] = INT_MAX;
        }
    }

    for (int i = 1; i <= numVertices - 1; i++) {
        for (int k = 0; k < numEdges; k++) {
            int u = edges[k].u;
            int v = edges[k].v;
            int weight = edges[k].weight;

            if (distance[u] != INT_MAX && distance[u] + weight < distance[v]) {
                distance[v] = distance[u] + weight;
            }
        }
    }

    for (int k = 0; k < numEdges; k++) {
        int u = edges[k].u;
        int v = edges[k].v;
        int weight = edges[k].weight;

        if (distance[u] != INT_MAX && distance[u] + weight < distance[v]) {
            printf("Negative Circle\n");
            return;
        }
    }
}

int main() {
    scanf("%d %d", &numVertices, &numEdges);

    for (int i = 0; i < numEdges; i++) {
        scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].weight);
    }

    int startVertex;
    scanf("%d", &startVertex);

    bellmanFord(startVertex);

    for (int i = 1; i <= numVertices; i++) {
        printf("Vertex %d: Distance = %d\n", i, distance[i]);
    }

    return 0;
}