import java.util.*;
public class BellmanFord {
  static boolean debug = false;
  static class Edge {
    int from, to, cost;
    public Edge(int from,int to,int cost) {
      this.from = from; this.to = to; this.cost = cost;
    }
    public String toString() { return "edge["+from+", "+to+", "+cost+"]"; }
  }
  int MAX_V;
  ArrayList<Edge> edges;
  int[] distance;
  public BellmanFord(int n,int m) {
    MAX_V = n;
    edges = new ArrayList<Edge>();
    distance = new int[n];
  }
  public void addEdge(int from, int to, int cost) {
    edges.add(new Edge(from,to,cost));
  }
  public void shortestPath(int src, int dst) {
    for (int i=0; i<distance.length; i++) distance[i] = Integer.MAX_VALUE;
    distance[src] = 0;
    int count = 0;
    boolean updated = true;
    while (updated) {
      updated = false;
      for (Edge e: edges) {
        if (distance[e.from] != Integer.MAX_VALUE
	    && distance[e.to] > distance[e.from] + e.cost) {
          distance[e.to] = distance[e.from] + e.cost;
          updated = true;
          if (count == MAX_V-1) throw new RuntimeException("negative loop");
        }
      }
      count ++;
    }
  }
  public static void main(String[] args) {
    for (int i=0; i<args.length; i++) {
      if (args[i].equals("-d")) debug = !debug;
    }
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt(), m = sc.nextInt();
    BellmanFord bf = new BellmanFord(n, m);
    for (int i=0; i<m; i++) {
      int from = sc.nextInt(), to = sc.nextInt(), cost = sc.nextInt();
      bf.addEdge(from,to,cost);
    }
    int src = sc.nextInt(), dst = sc.nextInt();
    try {
	bf.shortestPath(src,dst);
	System.out.println(bf.distance[dst]);
    } catch (Exception e) {
	System.out.println("negative loop");
    }
    if (debug) {
      for (int i=0; i<bf.MAX_V; i++) System.out.print(bf.distance[i]+" ");
      System.out.println();
    }
  }
}

$ javac BellmanFord.java
$ java BellmanFord < dg00.txt
7
$ java BellmanFord < dg01.txt
negative loop
$ java BellmanFord -d < dg00.txt
7
0 5 3 5 4 7 
$ java BellmanFord -d < dg01.txt
negative loop
0 0 -2 1 0 3 
$ java BellmanFord -d < dg02.txt
negative loop
0 5 3 5 4 7 -20 -21 -19 

6 9
0 1 5
0 2 4
1 2 -2
1 3 1
2 3 2
2 4 1
2 5 4
3 5 3
4 5 4
0 5

6 10
0 1 5
0 2 4
1 2 -2
1 3 1
2 3 2
2 4 1
2 5 4
3 1 -1
3 5 3
4 5 4
0 5

9 13
0 1 5
0 2 4
1 2 -2
1 3 1
2 3 2
2 4 1
2 5 4
3 5 3
4 5 4
3 6 -1
6 7 -1
7 8 -1
8 6 -1
0 5

#!/usr/bin/env python
import sys

Vn = 0
G = [{}]

def setNode(n):
  global G, Vn
  Vn = n
  G = [{} for i in range(Vn)]
def addEdge(s,t,w):
  global G
  G[s][t]=w
def solve(s,t):
  global G, Vn
  distance = [sys.maxsize for i in range(Vn)]
  distance[s] = 0
  count = 0
  updated = True
  while updated:
    updated = False
    for i in range(Vn):
      if distance[i] != sys.maxsize:
        for j in G[i]:
          d = distance[i] + G[i][j]
          if (d < distance[j]):
            distance[j] = d
            updated = True
            if count == Vn-1: raise NameError('negative loop')
    count += 1
  return distance[t]

n,m = map(int,input().split())
setNode(n)
for i in range(m):
  s,t,w = map(int,input().split())
  addEdge(s,t,w)
src, dst = map(int,input().split())
print(solve(src,dst))

$ python BellmanFord.py < dg00.txt 
7
$ python BellmanFord.py < dg01.txt  ← 負のループ
Traceback (most recent call last):
  File "/raid/nitta/public_html/lec/BellmanFord/python/BellmanFord.py", line 39, in <module>
    print(solve(src,dst))
  File "/raid/nitta/public_html/lec/BellmanFord/python/BellmanFord.py", line 29, in solve
    if count == Vn-1: raise NameError('negative loop')
NameError: negative loop
$ python BellmanFord.py < dg02.txt  ← 負のループ
Traceback (most recent call last):
  File "/raid/nitta/public_html/lec/BellmanFord/python/BellmanFord.py", line 39, in <module>
    print(solve(src,dst))
  File "/raid/nitta/public_html/lec/BellmanFord/python/BellmanFord.py", line 29, in solve
    if count == Vn-1: raise NameError('negative loop')
NameError: negative loop