Go: package main

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

//make priority queue
type Item struct {
	id       int
	priority int // this state is priority and distans from start
	index    int
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

// we want the ascending-priority-queue.
// So we use less than here.
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 = j
	pq[j].index = i
}

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
}

func (pq *PriorityQueue) update(dist int, id int) {
	for _, i := range *pq {
		if i.id == id {
			if i.priority > dist {
				i.priority = dist
			}
		}
	}
}

// the main code
func nextInt(sc *bufio.Scanner) int {
	sc.Scan()
	n, _ := strconv.Atoi(sc.Text())
	return n
}

func dikstra(dist *[][]int, n int) *[]int {
	// preparate priority queue
	inf := 1 << 30
	pq := make(PriorityQueue, n)
	shortests := make([]int, n)
	for i := 0; i < n; i++ {
		pq[i] = &Item{
			id:       i,
			priority: inf,
			index:    i,
		}

		shortests[i] = inf
	}
	pq[0].priority = 0
	shortests[0] = 0
	heap.Init(&pq)

	for pq.Len() > 0 {
		item := heap.Pop(&pq).(*Item)
		shortests[item.id] = item.priority
		for id, d := range (*dist)[item.id] {
			if d != -1 {
				pq.update(item.priority+d, id)
			}
		}
		heap.Init(&pq)
	}
	return &shortests
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	// init
	n := nextInt(sc)
	dist := make([][]int, n)
	for i := 0; i < n; i++ {
		dist[i] = make([]int, n)
		for j := 0; j < n; j++ {
			dist[i][j] = -1
		}
	}

	// std Input
	for i := 0; i < n; i++ {
		u := nextInt(sc)
		k := nextInt(sc)
		for j := 0; j < k; j++ {
			v, c := nextInt(sc), nextInt(sc)
			dist[u][v] = c
		}
	}

	shortests := dikstra(&dist, n)
	for i, d := range *shortests {
		fmt.Printf("%d %d\n", i, d)
	}
}

Python: #from heapdict import heapdict
import sys
import heapq
input=sys.stdin.readline

def dijkstra(G,start,n):#グラフ,初期頂点,頂点数
    INF=2<<28
    dist=[INF]*n;dist[start]=0
    used=[False]*n;used[start]=True
    q=[]

    for v in G[start]:
        heapq.heappush(q,v)
    
    while len(q)>0:
        now1,now2=heapq.heappop(q)
        #print(now1,now2)
        if used[now2]:
            continue
        v=now2
        dist[v]=now1
        used[v]=True

        for e1,e2 in G[v]:
            if not used[e2]:
                heapq.heappush(q,(e1+dist[v],e2))

    return dist

def main():
    N=int(input().rstrip())
    g=[[] for _ in range(N)]
    for _ in range(N):
        u,k,*c=map(int,input().split())
        for j in range(0,k*2,2):
            g[u].append((c[j+1],c[j]))

    ans=dijkstra(g,0,N)
    for i,x in enumerate(ans):
        print(i,x)

if __name__=="__main__":
    main()

Python: import heapq

INFTY = 1<<20

N = int(input())
M = [[] for _ in range(N)]
for i in range(N):
    u, k, *adjacents = map(int, input().split())
    for j in range(k):
        edge = adjacents[2*j]
        weight = adjacents[2*j+1]
        M[i].append((weight, edge))

mst = [False for _ in range(N)]
d = [INFTY for _ in range(N)]
d[0] = 0
pq = []
heapq.heappush(pq, (0, 0))

while len(pq) != 0:
    u = heapq.heappop(pq)
    u_edge = u[1]
    u_cost = u[0]

    mst[u_edge] = True

    if d[u_edge] < u_cost:
        continue

    for v in M[u_edge]:
        v_edge = v[1]
        v_cost = v[0]
        if mst[v_edge] == True:
            continue
        if d[u_edge]+v_cost < d[v_edge]:
            d[v_edge] = d[u_edge]+v_cost
            heapq.heappush(pq, (d[v_edge], v_edge))

for i in range(N):
    print("{} {}".format(i, d[i]))

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


def max_heapify(heap, i, heap_size):
    L = i * 2
    R = L + 1
    if L <= heap_size and heap[L][0] < heap[i][0]:
        largest = L
    else:
        largest = i
    if R <= heap_size and heap[R][0] < heap[largest][0]:
        largest = R
    if largest != i:
        heap[i], heap[largest] = heap[largest], heap[i]
        max_heapify(heap, largest, heap_size)


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

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

    weight = [[maxint, i] for i in xrange(num)]
    weight[0][0] = 0
    V = set(xrange(1, num))
    W = weight[:]
    wn = num
    index = 0

    while V:
        for v, cost in L[index]:
            if v not in V:
                continue
            weight[v][0] = min(weight[v][0], cost + weight[index][0])

        for i in xrange(wn//2, 0, -1):
            max_heapify(W, i, wn-1)
        index = W[1][1]
        W[1] = W[-1]
        wn -= 1
        del W[-1]
        V.remove(index)

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


main()

Python: inf = float('inf')
n = int(input())
g = []
for i in range(n):
    line = list(map(int, input().split()))
    k = line[1]
    c = [inf] * n
    for j in range(k):
        v = line[2 + 2 * j]
        c[v] = line[3 + 2 * j]
    g.append(c)

distance = [inf] * n
distance[0] = 0
visited = [False] * n
current = 0

while not all(visited):
    visited[current] = True
    min_i = 0
    min_d = inf
    for i in range(n):
        if not visited[i]:
            if distance[current] + g[current][i] < distance[i]:
                distance[i] = distance[current] + g[current][i]
            if distance[i] < min_d:
                min_i = i
                min_d = distance[i]
    current = min_i

for i in range(n):
    print(i, distance[i])

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

N = int(input())
INF = float("inf")
adj = [[] for _ in range(N)]

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


def dijkstra(adj):
    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 = pcost + 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(adj)