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

	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: #!/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 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]
        V.remove(index)

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


main()

Python: import sys

f_i = sys.stdin

n = int(f_i.readline())

adj = [[(int(cost), int(v_n)) for v_n, cost in zip(x.split()[2::2], x.split()[3::2])] for x in f_i]

import heapq

def dijkstra():
    PQ = []
    isVisited = [False] * n
    distance = [999900001] * n

    distance[0] = 0
    heapq.heappush(PQ, (0, 0))
    
    while PQ:
        uc = heapq.heappop(PQ)
        u = uc[1]

        if uc[0] > distance[u]:
            continue

        isVisited[u] = True
        
        for vc in adj[u]:
            v = vc[1]
            if isVisited[v] == True:
                continue
            t_cost = distance[u] + vc[0]
            if t_cost < distance[v]:
                distance[v] = t_cost
                heapq.heappush(PQ, (t_cost, v))

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


dijkstra()

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


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:
        swap = False
        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
                swap = True

        if swap:
            heapq.heapify(W)
        index = heapq.heappop(W)[1]
        V.remove(index)

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


main()

Python: import sys

f_i = sys.stdin

n = int(f_i.readline())

adj = [[(int(cost), int(v_n)) for v_n, cost in zip(x.split()[2::2], x.split()[3::2])] for x in f_i]

import heapq

def dijkstra():
    PQ = [(0, 0)]
    distance = [999900001] * n

    distance[0] = 0
    
    while PQ:
        uc = heapq.heappop(PQ)
        u = uc[1]
        
        for vc in adj[u]:
            v = vc[1]
            t_cost = distance[u] + vc[0]
            if t_cost < distance[v]:
                distance[v] = t_cost
                heapq.heappush(PQ, (t_cost, v))

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


dijkstra()

Python: from sys import stdin
import heapq
INF = 1<<21
n = int(stdin.readline())
adj = [[]] * n
for u in range(0, n):
    U = list(map(int, stdin.readline().split()[2:]))
    adj[u] = zip(U[0::2], U[1::2])
def dijkstra():
    d = [0] + [INF] * (n - 1)
    hq = [(0, 0)]
    while hq:
        u = heapq.heappop(hq)[1]
        for v, c in adj[u]:
            alt = d[u] + c
            if d[v] > alt:
                d[v] = alt
                heapq.heappush(hq, (alt, v))
    for i, c in enumerate(d):
        print(i, c)
dijkstra()

Python: from queue import PriorityQueue

def sssp(adj_list):
    n = len(adj_list)
    d = [None]*n
    pq = PriorityQueue()
    pq.put((0, 0)) # d, v

    while(not pq.empty()):
        d_v, v = pq.get()
        if d[v] is not None:
            continue
        d[v] = d_v
        for u, c_vu in adj_list[v]:
            pq.put((d[v]+c_vu, u))

    return d


if __name__ == '__main__':
    n = int(input())
    adj_list = []
    for _ in range(n):
        adj_list.append([])

    for _ in range(n):
        l = list(map(int, input().rstrip().split(' ')))
        u = l[0]
        k = l[1]
        adj_list_for_u = []
        for v, c in zip(l[2::2], l[3::2]):
            adj_list_for_u.append((v,c))
        adj_list[u] = adj_list_for_u

    d = sssp(adj_list)
    for u, d_u in zip(range(n), d):
        print (u, d_u)

Python: from heapq import heappop, heappush

def dijkstra(s):
    dp[s] = 0
    hq = []
    used[s] = 0
    for i in cost[s]:
        heappush(hq, i)

    while hq:
        minv = heappop(hq)
        if used[minv[1]] == 0:
            continue
        v = minv[1]
        dp[v] = minv[0]
        used[v] = 0
        for i in cost[v]:
            if used[i[1]]:
                heappush(hq, [i[0] + dp[v], i[1]])
    return

INF = 10 ** 18
n = int(input())
cost = [[] for _ in range(n)]
used = [1] * n
dp = [INF] * n

for i in range(n):
    lst = list(map(int, input().split()))
    for j in range(lst[1]):
        v, c = lst[2 + (2 * j)], lst[3 + (2 * j)]
        cost[lst[0]].append([c, v])

dijkstra(0)
for i in range(n):
    print(i, dp[i])