# グラフgと始点s
# 負のサイクルがある場合Trueを返す
bellmanFord(g, s):
    for v ← 0 to g.N-1:
        dist[v] ← INF   

    dist[s] ← 0

    for t ← 0 to N-1:
        updated ← False
        for u ← 0 to g.N-1:
            if dist[u] = INF: continue
            for e in g.adjLists[u]:         
                if dist[e.v] > dist[u] + e.weight
                    dist[e.v] ← dist[u] + e.weight
                    updated ← True
                    if t = N-1:
                        return True  # 負のサイクルを検知

        if not updated: break # 更新がなければ終了

    return false # 負のサイクルは存在しない