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: import heapq

INF = 1e9

n = int(input())
adj_list = [[]] * n

for u in range(n):
    U = list(map(int, input().split()[2:]))
    adj_list[u] = zip(U[0::2], U[1::2]) # adj_list[u] = (v, cost)


def dijkstra(x):
    d = [INF] * x
    d[0] = 0
    isVisited = [False] * x
    hq = [(0, 0)] # (distance, v)??????????????¬??????????????????(key, ????´?)???????????????push, pop?????????
    
    while hq:
        u = heapq.heappop(hq)[1]
        isVisited[u] = True
        
        for v, c in adj_list[u]:
            if not isVisited[v] and d[v] > d[u] + c:
                d[v] = d[u] + c
                heapq.heappush(hq, (d[u] + c, v))
                
    return d

for i, di in enumerate(dijkstra(n)):
    print(i,di)

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


def heap_increase_key(heap, i):
    parent = i // 2
    while i > 1 and heap[parent][0] > heap[i][0]:
        heap[i], heap[parent] = heap[parent], heap[i]
        i //= 2
        parent = i // 2


def min_heapify(heap, i):
    heap_size = len(heap)-1
    L = i * 2
    R = L + 1
    if L <= heap_size and heap[L][0] < heap[i][0]:
        smallest = L
    else:
        smallest = i
    if R <= heap_size and heap[R][0] < heap[smallest][0]:
        smallest = R
    if smallest != i:
        heap[i], heap[smallest] = heap[smallest], heap[i]
        min_heapify(heap, smallest)


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 = [0] + weight[1:]
    index = 0

    while V:
        i = maxint
        for v, cost in L[index]:
            if v not in V:
                continue
            cost += weight[index][0]
            if weight[v][0] > cost:
                weight[v][0] = cost
                heap_increase_key(W, W.index(weight[v]))
            #weight[v][0] = min(weight[v][0], cost + weight[index][0])

        index = W.pop(1)[1]
        min_heapify(W, 1)
        V.remove(index)

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


main()

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


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[1:]
    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])

        a = min(W, key=itemgetter(0))
        index = a[1]
        W.remove(a)
        V.remove(index)

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


main()

Python: from heapq import heappush, heappop

INF = 10000 * 100000

def dijkstra(s: int):
	d[s] = 0
	H = []
	for v in range(n):
		heappush(H, (d[v], v))
	while len(H) >= 1:
		_, u = heappop(H)
		color[u] = "BLACK"
		for v, c in M[u]:
			if color[v] != "BLACK" and d[u] + c < d[v]:
				d[v] = d[u] + c
				pi[v] = u
				color[v] = "GRAY"
				heappush(H, (d[v], v))

if __name__ == "__main__":
	n = int(input())
	G = []
	M = [[] for _ in range(n)]
	color = ["WHITE" for _ in range(n)]
	d = [INF for _ in range(n)]
	pi = [None for _ in range(n)]

	for _ in range(n):
		l = list(map(int, input().split()))
		u = l[0]
		k = l[1]
		for i in range(k):
			v = l[2 * (i + 1)]
			c = l[2 * (i + 1) + 1]
			M[u].append([v, c])
	dijkstra(0)
	for v in range(n):
		print(f"{v} {d[v]}")

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

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

searched = [False for _ in range(N)]
searched[0] = True

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

heap = [[0, 0]]

while len(heap):
    pcost, p = heappop(heap)
    searched[p] = True
    
    if d[p] < pcost:
        continue
    
    for v, c in adj[p]:
        if not searched[v]:
            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]))

Python: import sys
import heapq
from collections import namedtuple
inf = float('inf')
Node = namedtuple('Node', 'd, no')

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def SSSP(n, Adj):
    d = [inf] * n
    p = [-1] * n
    checked = [False] * n
    d[0] = 0
    checked[0] = True
    heap = [Node(d[0], 0)]

    while heap:
        u = heapq.heappop(heap)

        if d[u.no] < u.d:
            continue

        checked[u.no] = True

        for v, cost in Adj[u.no]:
            if not checked[v] and d[u.no] + cost < d[v]:
                d[v] = d[u.no] + cost
                p[v] = u.no
                heapq.heappush(heap, Node(d[v], v))

    return d

def solve():
    n = int(input())
    Adj = [[] for i in range(n)]

    for i in range(n):
        u, k, *line = [int(i) for i in input().split()]
        for j in range(k):
            Adj[u].append((line[2*j], line[2*j + 1]))

    # debug(Adj, locals())

    d = SSSP(n, Adj)

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

if __name__ == '__main__':
    solve()