Network Delay Time (Leetcode 743)

Problem Link: https://leetcode.com/problems/network-delay-time/

from collections import defaultdict
import heapq
class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        
        adj=defaultdict(list)
        for i in times:
            adj[i[0]].append((i[1],i[2]))
        
        pq=[]
        heapq.heapify(pq)
        distances=[float('inf') for i in range(n+1)]
        # 1 based indexing
        distances[0]=0
        distances[k]=0
        # node, dist
        heapq.heappush(pq,(k,0))
        
        while(len(pq)>0):
            
            node, dist = heapq.heappop(pq)
            for i in adj[node]:
                adjnode=i[0]
                weight=i[1]
                if(dist+weight<distances[adjnode]):
                    distances[adjnode]=dist+weight
                    heapq.heappush(pq,(adjnode,distances[adjnode]))
        maxx=-1
        for i in range(1,n+1):
            if(distances[i]==float('inf')):
                return -1
            maxx=max(maxx,distances[i])
        return maxx