ダイクストラ法(Python2) http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_12_B

dijkstra.py

import heapq

def dijkstra(G, s):
    n = len(G)
    INF = float("inf")
    d = [INF] * n
    d[s] = 0
    pq = []
    heapq.heappush(pq, (0, s)) # (cost, vertex)
    while pq:
        c, v = heapq.heappop(pq)
        if d[v] < c:
            continue
        for nv, nc in G[v]:
            if d[nv] > d[v] + nc:
                d[nv] = d[v] + nc
                heapq.heappush(pq, (d[nv], nv))
    return d

n = input()
G = [[] for i in xrange(n)]
for i in xrange(n):
    li = map(int, raw_input().split())
    for j in xrange(li[1]):
        G[i].append((li[2 * (j + 1)], li[2 * (j + 1) + 1]))

d = dijkstra(G, 0)
for i, c in enumerate(d):
    print i, c