ALDS1_12_C: Single Source Shortest Path II

問題は変わらず制約のみが変更に
頂点の数が100までだったのが10000までに
実際、Iのコードでジャッジしても頂点の数が1000までは通る
頂点の数が10000でTLE

問題文を読んでもIからどうやりかたを変えればというヒントはない
ヒントになりそうなのは図
三角形が書けたような図形が追加されている
これはなんだったかな？ヒープか？
優先度付きキューだ
そういえばあとで優先度付きキューを使って高速化しますよって
どっかに書いてあった

どこで使うのかと言うと
ここでキューに入れて

        for adj, c in min_node.adjs:
            if min_node.dist + c < adj.dist:
                adj.dist = min_node.dist + c
                adj.color = Node.GRAY

ここで取り出す、ってことなんだろうな

        min_node = min(
            [n for n in nodes if n.color != Node.BLACK],
            default=None, key=lambda n: n.dist)

出し入れはいいとして、更新があるよな
どうしたらいいんだ