Go: package main

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

// I/O
type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextFloat() float64 {
	f, e := strconv.ParseFloat(s.nextStr(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *Scanner) nextRuneSlice() []rune {
	return []rune(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func (s *Scanner) nextFloatSlice(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextFloat()
	}
	return res
}

// Arithmetic
func max(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m < i {
			m = i
		}
	}
	return m
}

func min(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m > i {
			m = i
		}
	}
	return m
}

func abs(x int) int {
	if x > 0 {
		return x
	}
	return -x
}

func pow(x, y int) int {
	res := 1
	for i := 0; i < y; i++ {
		res *= x
	}
	return res
}

func ceil(a, b int) int {
	if a%b == 0 {
		return a / b
	} else {
		return a/b + 1
	}
}

// Sort
type RuneSlice []rune

func (a RuneSlice) Len() int           { return len(a) }
func (a RuneSlice) Less(i, j int) bool { return a[i] < a[j] }
func (a RuneSlice) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

// Main
const INF = 1 << 60

type Edge struct {
	to, cost int
}

type Node struct {
	id, cost int
}

type PQ []Node

func (pq PQ) Len() int           { return len(pq) }
func (pq PQ) Less(i, j int) bool { return pq[i].cost < pq[j].cost }
func (pq PQ) Swap(i, j int)      { pq[i], pq[j] = pq[j], pq[i] }

func (pq *PQ) Push(x interface{}) {
	*pq = append(*pq, x.(Node))
}

func (pq *PQ) Pop() interface{} {
	old := *pq
	n := len(old)
	x := old[n-1]
	*pq = old[0 : n-1]
	return x
}

func main() {
	sc := NewScanner()
	wtr := bufio.NewWriter(os.Stdout)
	N := sc.nextInt()
	E := make([][]Edge, N)
	for i := 0; i < N; i++ {
		id, k := sc.nextInt(), sc.nextInt()
		E[id] = make([]Edge, k)
		for j := 0; j < k; j++ {
			to, cost := sc.nextInt(), sc.nextInt()
			E[id][j] = Edge{to, cost}
		}
	}

	d := make([]int, N)
	for i := 0; i < N; i++ {
		d[i] = INF
	}
	done := make([]bool, N)
	pq := &PQ{}
	heap.Init(pq)
	d[0] = 0
	heap.Push(pq, Node{0, 0})
	for pq.Len() > 0 {
		cur := heap.Pop(pq).(Node).id
		if done[cur] {
			continue
		}
		done[cur] = true
		for i := 0; i < len(E[cur]); i++ {
			to, cost := E[cur][i].to, E[cur][i].cost+d[cur]
			if !done[to] && cost < d[to] {
				d[to] = cost
				heap.Push(pq, Node{to, cost})
			}
		}
	}

	for i := 0; i < N; i++ {
		fmt.Fprintln(wtr, i, d[i])
	}
	wtr.Flush()
}

Python: # -*- coding: utf-8 -*-
from heapq import heappop, heappush
def inpl(): return list(map(int, input().split()))
INF = float("inf")
N = int(input())
G = []
for _ in range(N):
    I = inpl()
    G.append(zip(*[I[3::2], I[2::2]]))

def dijkstra(G):
    C = [INF]*(N)
    C[0] = 0
    visited = [False] * (N)
    Q = [[0, 0]]

    while Q:
        c, u = heappop(Q)
        if C[u] < c:
            continue
        visited[u] = True
        for d, v in G[u]:
            if visited[v]:
                continue
            e = c + d
            if e < C[v]:
                C[v] = e
                heappush(Q, [e, v])
    return C

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

Python: import heapq as hp

INF = 1000000

def diikstraMethd(G, s):
    # ?????????
    n = len(G)
    d = [INF for _ in range(n)]
    d[s] = 0
    PQ = [(d[s], s)]

    while PQ:
        u = hp.heappop(PQ)[1]
        for v, c in G[u]:
            alt = d[u] + c
            if d[v] > alt:
                d[v] = alt
                hp.heappush(PQ, (alt, v))

    return d


if __name__ == '__main__':
    n = int(input())
    G = [ [] for _ in range(n)]
    for _ in range(n):
        tmp = list(map(int, input().split()))
        u = tmp.pop(0)
        k = tmp.pop(0)
        for i in range(k):
            v = tmp.pop(0)
            c = tmp.pop(0)
            G[u].append((v, c))

    d = diikstraMethd(G, 0)

    for i in range(n):
        print('{0} {1}'.format(i, d[i]))

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


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))
    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)

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


main()

Python: #coding:utf-8
import numpy as np

n = int(input())
inf = 1000000000000000

def minHeapify(Q,i):
    H = len(Q)
    l = 2*i
    r = 2*i + 1
    if l < H and Q[l][1] < Q[i][1]:
        smallest = l
    else:
        smallest = i
    if r < H and Q[r][1] < Q[smallest][1]:
        smallest = r

    if smallest != i:
        Q[i], Q[smallest] = Q[smallest], Q[i]
        minHeapify(Q,smallest)

def buildMinHeap(Q):
    H = len(Q)
    for i in range(H // 2, -1, -1):
        minHeapify(Q,i)

def Insert(Q,key):
    v = key[0]
    Q.append([v,inf])
    lens = len(Q)
    heapIncreaseKey(Q,lens-1,key)

def heapIncreaseKey(Q,i,key):
    Q[i][1] = key[1]
    while i > 0 and Q[i // 2][1] > Q[i][1]:
        Q[i], Q[i // 2] = Q[i // 2], Q[i]
        i //= 2

def heapExtractMin(Q):
    H = len(Q)
    minv = Q[0][0]
    Q[0] = Q[H-1]
    Q.pop()
    minHeapify(Q,0)
    return minv




def dijkstra(s):
    color = ["white" for i in range(n)]
    d = [inf for i in range(n)]
    d[s] = 0
    Q = [[s,0]]
    while Q != []:
        u = heapExtractMin(Q)
        color[u] = "black"
        for vw in mtrx[u]:
            [v,w] = vw
            if color[v] != "black":
                if d[u] + w < d[v]:
                    d[v] = d[u] + w
                    color[v] = "gray"
                    Insert(Q,[v,d[v]])
    return d



mtrx = [[] for i in range(n)]
for i in range(n):
    col = list(map(int,input().split()))
    u,k = col[0], col[1]
    for j in range(k):
        [v,w] = col[2*j+2: 2*j+4]
        mtrx[u].append([v,w])



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