[编程题]仓库配送（最短路, Dijskra）

[编程题]仓库配送

# 最短路径, Dijskra
from cmath import cos
from heapq import *
from collections import defaultdict


N, K, M = list(map(int, input().strip().split()))
G = defaultdict(set)
for i in range(M):
    v, u, w = list(map(int, input().strip().split()))
    G[v].add((u, w))

def dijskra(start, G, N):

    visit, q, ans = set(), [(0, start)], 0

    while q:
        cost, v = heappop(q)
        if v in visit: continue
        visit.add(v)
        ans = max(ans, cost)
        for u, w in G[v]:
            if u not in visit:
                heappush(q, (cost + w, u))
        if len(visit) == N: return ans
    
    return -1

ans = dijskra(K, G, N)
print(ans)