Problem p03452 (python)

Fixed submission:
from collections import defaultdict, deque

n,m = map(int,input().split())
edge = [[] for i in range(n)]
for i in range(m):
    l,r,d = map(int, input().split())
    edge[l-1].append((r-1,d))
    edge[r-1].append((l-1,-d))

dist = [0]*n
visited = [False]*n

for i in range(n):
    if visited[i]:
        continue
    q = deque()
    q.append((i,0))
    while q:
        to, d = q.popleft()
        if visited[to]:
            if dist[to] != d:
                print("No")
                exit()
        else:
            visited[to] = True
            dist[to] = d
            for ind, j in edge[to]:
                q.append((ind,d+j))

print("Yes")

Buggy submission (verdict: Runtime Error):
def LI(): return list(map(int, input().split()))
def LS(): return input().split()
def I(): return int(input())
def S(): return input()

import networkx as nx

n, m = LI()
l = []
for i in range(m):
    l.append(LI())
edge = []
graph1 = [[float("inf")]*n for i in range(n)]
graph2 = [[float("inf")]*n for i in range(n)]
dic1 = {}
dic2 = {}
for i in range(m):
    if l[i][0]-1 not in dic1:
       dic1[l[i][0]-1] = 1
    else:
        dic1[l[i][0]-1] += 1
    if l[i][1]-1 not in dic2:
       dic2[l[i][1]-1] = 1
    else:
        dic2[l[i][1]-1] += 1 
    edge.append([l[i][0], l[i][1]])
    graph1[l[i][0] - 1][l[i][1] - 1] = l[i][2]
    graph2[l[i][0] - 1][l[i][1] - 1] = -l[i][2]
G = nx.DiGraph()
G.add_edges_from(edge)
try:
    a = nx.topological_sort(G)
except:
    print("No")
    exit()
# print(a)

# 向きありグラフ
# 矛盾する時、距離正の閉路が存在(1→3, 3と３→1, 2)、距離を持つ(i,j)に対して全てのパスの距離が違う(最小 != 最大 1→2→3 1→4→3)
# グラフを作った後、前者はトポロジカルソート、 後者はダイクストラと、最長距離は辺の値を負にするためダイクストラが使えない?→いや使える全部負ならok

# 閉路が無い時、1→3→5 と1→4→5 を判定できない(V^3)
# ２つ以上のパスを持つところをリストでもっておいて探索
s = []
e = []
for i in dic1.keys():
    if dic1[i] > 1:
        s.append(i)
for i in dic2.keys():
    if dic2[i] > 1:
        e.append(i)
# print(s,e)

import heapq

class Dijkstra(object):
    def dijkstra(self, adj, start, goal=None):
        '''
        ダイクストラアルゴリズムによる最短経路を求めるメソッド
        入力
        adj: adj[i][j]の値が頂点iから頂点jまでの距離(頂点iから頂点jに枝がない場合，値はfloat('inf'))となるような2次元リスト(正方行列)
        start: 始点のID
        goal: オプション引数．終点のID
        出力
        goalを引数に持つ場合，startからgoalまでの最短経路を格納したリストを返す
        持たない場合は，startから各頂点までの最短距離を格納したリストを返す
        >>> d = Dijkstra()
        >>> d.dijkstra([[float('inf'), 2, 4, float('inf'), float('inf')], [2, float('inf'), 3, 5, float('inf')], [4, 3, float('inf'), 1, 4], [float('inf'), 5, 1, float('inf'), 3], [float('inf'), float('inf'), 4, 3, float('inf')]], 0)
        [0, 2, 4, 5, 8] # 例えば，始点0から頂点3までの最短距離は5となる
        >>> d.dijkstra([[float('inf'), 2, 4, float('inf'), float('inf')], [2, float('inf'), 3, 5, float('inf')], [4, 3, float('inf'), 1, 4], [float('inf'), 5, 1, float('inf'), 3], [float('inf'), float('inf'), 4, 3, float('inf')]], 0, goal=4)
        [0, 2, 4] # 頂点0から頂点4までの最短経路は0 -> 2 -> 4となる
        '''
        num = len(adj)          # グラフのノード数
        dist = [float('inf') for i in range(num)] # 始点から各頂点までの最短距離を格納する
        prev = [float('inf') for i in range(num)] # 最短経路における，その頂点の前の頂点のIDを格納する
        
        dist[start] = 0
        q = []                  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
        heapq.heappush(q, (0, start)) # 始点をpush

        while len(q) != 0:
            prov_cost, src = heapq.heappop(q) # pop
            
            # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
            if dist[src] < prov_cost:
                continue

            # 他の頂点の探索
            for dest in range(num):
                cost = adj[src][dest]
                if cost != float('inf') and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost # distの更新
                    heapq.heappush(q, (dist[dest], dest)) # キューに新たな仮の距離の情報をpush
                    prev[dest] = src                      # 前の頂点を記録
                    
        if goal is not None:
            return self.get_path(goal, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        '''
        始点startから終点goalまでの最短経路を求める
        '''
        path = [goal]           # 最短経路
        dest = goal

        # 終点から最短経路を逆順に辿る
        while prev[dest] != float('inf'):
            path.append(prev[dest])
            dest = prev[dest]

        # 経路をreverseして出力
        return list(reversed(path))

flag = True
for i in s:
    test = Dijkstra()
    k1 = test.dijkstra(graph1,i)
    k2 = test.dijkstra(graph2, i)
    for j in e:
        if abs(k1[j]) != abs(k2[j]):
            flag = False
            print("No")
            exit()
            break
    if flag == False:
        break
if flag:
    print("Yes")