#2024s

# 十分に大きい数（INF）の定義
INF = 999999


def distance(N, edge, GOAL):
    # 6: 始点からの距離配列（1から始まるため N+1 個確保。初期値は INF）
    dist = [INF] * (N + 1)

    # 7: 最短距離が確定したかを記録する配列（初期値は 0）
    done = [0] * (N + 1)

    # 図3: 最短経路を逆算して出力するための配列（初期値は 0）
    viaNode = [0] * (N + 1)

    # 11: 始点の始点ノード距離を 0 とする
    dist[1] = 0

    # 12: while (true)
    while True:
        # 13: 最小値を探すための一時変数を初期化
        minDist = INF
        curNode = -1

        # 14-19: 未確定ノードの中から距離が最小のノード（更新起点ノード）を探す
        for k in range(1, N + 1):
            # [イ]: dist[k] < minDist
            if done[k] == 0 and dist[k] < minDist:
                minDist = dist[k]  # [ウ]
                curNode = k

        # すべてのノードが処理されたか、到達不可能な場合ループを抜ける
        if curNode == -1:
            break

        # 20: 最短距離を確定させる
        done[curNode] = 1

        # 21-23: 更新起点ノードが終点（GOAL）であれば、処理を終了して距離を返す
        if curNode == GOAL:
            # --- 最短経路の出力処理（図4） ---
            print("--- 最短経路（逆順） ---")
            j = GOAL
            print(f"ノード {GOAL} (終点)")
            while j > 1:
                # 経由したノードを出力して、前に戻る
                print(f"  ← ノード {viaNode[j]}")
                j = viaNode[j]
            print("-------------------------")

            return dist[curNode]

        # 24-28: 新しく確定した curNode を経由して、隣接ノード k への距離を更新する
        for k in range(1, N + 1):
            # [エ]: dist[curNode] + edge[curNode][k]
            # 未確定ノードかつ、新しいルートの方が近い場合
            new_dist = dist[curNode] + edge[curNode][k]
            if new_dist < dist[k] and done[k] == 0:
                dist[k] = new_dist
                viaNode[k] = curNode  # [オ]: 経路（直前のノード）を保存


# --- テスト用の実行コード ---
if __name__ == "__main__":
    # ノード数
    N = 5
    GOAL = 5

    # 4: 隣接行列 edge（問題の「図1」を再現）
    # 隣接していないペアには INF を格納。1始まりにするため 6x6 で作成。
    edge = [
        [INF, INF, INF, INF, INF, INF],  # 0行目（不使用）
        [INF, INF, 10, 16, INF, INF],  # V1 からの距離
        [INF, 10, INF, 4, 3, INF],  # V2 からの距離
        [INF, 16, 4, INF, 2, 3],  # V3 からの距離
        [INF, INF, 3, 2, INF, 6],  # V4 からの距離
        [INF, INF, INF, 3, 6, INF],  # V5 からの距離
    ]

    # 関数の実行
    shortest_distance = distance(N, edge, GOAL)
    print(f"始点(V1)から終点(V{GOAL})までの最短距離: {shortest_distance}")