classSolution:

defgetMinRiskValue(self,N,M,X,Y,W):

parent=list(range(N+1))

deffind(x):

edges=sorted(zip(W, X, Y))

MST_edges= []

for edgein edges:

if union(edge[1], edge[2]):

MST_edges.append(edge)

if find(0)== find(N):

MST= collections.defaultdict(list)

target= find(0)

for w, u, vinMST_edges:

if find(u)== targetand find(v)== target:

MST[u].append((v, w))

MST[v].append((u, w))

dfs= [(0,None,float('-inf'))]

while dfs:

v, p, max_w= dfs.pop()

for n, winMST[v]:

cur_max_w=max(max_w, w)

if n== N:

return cur_max_w

if n!= p:

dfs.append((n, v, cur_max_w))

for w, x, yin edges:

if union(x, y)and find(0)== find(N):# early return without constructing MST

return w