# 2026/10/01

inf = float("inf")

def bellman_ford(Es, V, s):
    """
    単一始点最短経路と、負の閉路の影響を受ける頂点を求める
    入力: 全ての辺Es (要素が (u, v, cost) のタプルリスト), 頂点数V, 開始点 s
    出力: (最短経路のリスト dis, 負の閉路の影響を受けるかの真偽値リスト negative)
    計算量: O(|E||V|)
    """
    dis = [inf] * V
    dis[s] = 0
    
    # 1. V-1回目までの更新（最短経路の計算）
    for _ in range(V - 1):
        for u, v, cost in Es:
            if dis[u] != inf and dis[u] + cost < dis[v]:
                dis[v] = dis[u] + cost

    # 2. V回目以降の更新（負の閉路の影響を受ける頂点の検出と伝播）
    negative = [False] * V
    for _ in range(V):
        for u, v, cost in Es:
            # V回目以降でも値が更新されるなら、その頂点は負の閉路の影響下にある
            if dis[u] != inf and dis[u] + cost < dis[v]:
                dis[v] = dis[u] + cost
                negative[v] = True
            # 負の閉路の影響を受けた頂点から到達可能な頂点も、すべて影響下とする
            if negative[u]:
                negative[v] = True
                
    return dis, negative