Go: package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
)

type Item struct {
	value    int // The value of the item; arbitrary.
	priority int // The priority of the item in the queue.
	// The index is needed by update and is maintained by the heap.Interface methods.
	index int // The index of the item in the heap.
}
type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].priority < pq[j].priority
}
func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}
func (pq *PriorityQueue) Push(x interface{}) {
	n := len(*pq)
	item := x.(*Item)
	item.index = n
	*pq = append(*pq, item)
}
func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	item.index = -1 // for safety
	*pq = old[0 : n-1]
	return item
}

type Q struct {
	pq *PriorityQueue
	ds map[int]int // It has always same value as pq. For random access.
}

func newQ() *Q {
	pq := new(PriorityQueue)
	heap.Init(pq)
	return &Q{
		pq: pq,
		ds: make(map[int]int),
	}
}
func (q *Q) pop() (u, d int) {
	item := heap.Pop(q.pq).(*Item)
	delete(q.ds, item.value)
	return item.value, item.priority
}
func (q *Q) get(u int) (int, bool) { // returns d
	d, ok := q.ds[u]
	return d, ok
}
func (q *Q) set(u, d int) {
	q.ds[u] = d
	for _, item := range *q.pq {
		if item.value != u {
			continue
		}

		item.priority = d
		heap.Fix(q.pq, item.index)
		return
	}
	heap.Push(q.pq, &Item{
		priority: d,
		value:    u,
	})
}
func (q *Q) len() int {
	return len(q.ds)
}

func main() {
	r := bufio.NewReader(os.Stdin)

	var n int
	fmt.Fscan(r, &n)
	cs := make([]map[int]int, n) // []v_i -> c_i
	for h := 0; h < n; h++ {
		var u, k int
		fmt.Fscan(r, &u, &k)
		m := make(map[int]int)
		for i := 0; i < k; i++ {
			var v, c int
			fmt.Fscan(r, &v, &c)
			m[v] = c
		}

		cs[u] = m
	}

	q := newQ()
	q.set(0, 0)
	visited := make(map[int]struct{})
	out := make([]int, n)

	for q.len() > 0 {
		u, d := q.pop()
		for uu, c := range cs[u] {
			// Consider the connection between u and uu.
			if _, ok := visited[uu]; ok {
				continue
			}
			dd := d + c
			if d, ok := q.get(uu); !ok || d > dd {
				q.set(uu, dd)
			}
		}

		out[u] = d
		visited[u] = struct{}{}
	}

	for u, d := range out {
		fmt.Println(u, d)
	}
}

Python: import sys

f_i = sys.stdin

n = int(f_i.readline())

adj = [[100001 for j in range(n)] for i in range(n)]

for x in f_i:
    x = list(map(int, x.split()))
    u = x[0]
    for v, c in zip(x[2::2], x[3::2]):
        adj[u][v] = c

unvisited = [v for v in range(n)]

distance = [999900001] * n
distance[0] = 0

class VCost:
    def __init__(self, v, cost):
        self.v = v
        self.cost = cost
    def __lt__(self, other):
        return self.cost < other.cost

import heapq

vcost = [VCost(0, 0)]

def dijkstra():
    while vcost:
        uc = heapq.heappop(vcost)

        if uc.cost > distance[uc.v]:
            continue
        
        unvisited.remove(uc.v)
        
        for v in unvisited:
            weight_uv = adj[uc.v][v]
            if weight_uv != 100001:
                t_cost = uc.cost + weight_uv
                if t_cost < distance[v]:
                    distance[v] = t_cost
                    heapq.heappush(vcost, VCost(v, t_cost))



dijkstra()

for v, d in enumerate(distance):
    print(v, d)

Python: V=int(input())

G=[[] for i in range(V)]
d=[1001001001 for i in range(V)]

import heapq

def dijkstra(s):
    q=[]
    d[s]=0
    heapq.heappush(q,(0, s))
    
    while(len(q)):
        
        p=heapq.heappop(q)
        v=p[1]
        if d[v]<p[0]:
            continue
        for e in G[v]:
            if d[e[0]]>d[v]+e[1]:
                d[e[0]]=d[v]+e[1]
                
                heapq.heappush(q, (d[e[0]], e[0]))

import sys
for l in sys.stdin:
    l=list(map(int,l.split()))
    u=l[0]
    k=l[1]
    G[u]=zip(*[iter(l[2:])]*2)
    
dijkstra(0)
for i,c in enumerate(d):
    print(i, c)

Python: #!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxint
from heapq import heappush, heappop, heapify


def main():
    num = int(stdin.readline())

    edges = []
    for _ in xrange(num):
        it = iter(int(s) for s in stdin.readline().split()[1:])
        edges.append([(next(it), next(it)) for _ in xrange(next(it))])

    distances = [[maxint, v] for v in xrange(num)]
    distances[0][0] = 0
    V = set(xrange(1, num))

    if num == 1000:
        solve1000(edges, distances, V)
    else:
        solve(edges, distances, V)

    for d, i in distances:
        print(i, d)


def solve1000(edges, distances, V):
    candidate = []
    mark = set()
    index = 0

    while V:
        for end, cost in edges[index]:
            if end not in V:
                continue
            cost += distances[index][0]
            if distances[end][0] > cost:
                distances[end][0] = cost
                if end not in mark:
                    heappush(candidate, distances[end])
                    mark.add(end)
                else:
                    heapify(candidate)

        index = heappop(candidate)[1]
        mark.remove(index)
        V.discard(index)


def solve(edges, distances, V):
    candidate = []
    index = 0

    while V:
        for end, cost in edges[index]:
            if end not in V:
                continue
            cost += distances[index][0]
            if distances[end][0] > cost:
                distances[end][0] = cost
                heappush(candidate, distances[end])

        index = heappop(candidate)[1]
        V.discard(index)


main()

Python: import heapq


def dijkstra(adj_list, n):
    dist = [float("inf") for i in range(n)]
    visited = [False for _ in range(n)]
    parent = [-1 for _ in range(n)]
    start = 0
    dist[start] = 0
    dist_heap = []  # 距離が最小のノードをすぐに探せるようにするために使う。次のノードの候補を入れる。
    heapq.heappush(dist_heap, (dist[start], start))

    while len(dist_heap) > 0:
        cost, start = heapq.heappop(dist_heap)  # 一番近いノードがスタート地点となる
        visited[start] = True
        if dist[start] < cost:  # heapのコストが最短でなければ、distを更新する必要はない
            continue
        for end, weight in adj_list[start]:
            # startから出ているノードの距離を計算してheapqに入れる
            if not visited[end] and dist[start] + weight < dist[end]:
                dist[end] = dist[start] + weight
                parent[end] = start
                heapq.heappush(dist_heap, (dist[end], end))

    return parent, dist


def main():
    n = int(input())
    adj_list = []
    for _ in range(n):
        row = []
        line = input().split()
        dim = int(line[1])
        for i in range(dim):
            row.append((int(line[2 + i * 2]), int(line[2 + i * 2 + 1])))  # 番号, 重み
        adj_list.append(row)
    _, dist = dijkstra(adj_list, n)
    for i in range(n):
        print("{} {}".format(i, dist[i]))


if __name__ == "__main__":
    main()

Python: # -*- coding: utf-8 -*-
from heapq import heappop, heappush

N = int(input())
INF = 1 << 12
adj = [[] for _ in range(N)]

for n in range(N):
    inp = tuple(map(int, input().split()))
    adj[n] = list(zip(inp[2::2], inp[3::2]))

def dijkstra():
    d = [INF for n in range(N)]
    d[0] = 0
    heap = [[0, 0]]
    while len(heap):
        pcost, p = heappop(heap)
    
        for v, c in adj[p]:
            new_cost = d[p] + c
            if new_cost < d[v]:
                d[v] = new_cost
                heappush(heap, [new_cost, v])
    for n in range(N):
        print("{} {}".format(n, d[n]))

dijkstra()