Go: package main

import (
	"fmt"
	"os"
	"bufio"
	"strings"
	"strconv"
)
var MAX = 1000000
type Vertex struct{
	Value int
	Routes map[int]int
	Done bool
}
func NewVertex(value int) *Vertex{
	routes := make(map[int]int)
	// for i, _ := range routes {
	// 	routes[i] = MAX
	// }
	return &Vertex{ value, routes, false }
}

func (v *Vertex) SetRoute(key, weight int) {
	v.Routes[key] = weight
}

type Path struct {
	Key int
	Weight int
}

var count = 0
func ShortestRoutes(list []*Vertex) []int {
	// create result table
	result  := make([]int, len(list))
	// fmt.Println(result)
	for i, _ := range result {
		result[i] = MAX
	}

	queue := make([]Path, 0)
	queue = append(queue, Path{0, 0})
	result[0] = 0

	for len(queue) != 0 {
		count++
		path := queue[0]
		queue = queue[1:]
		for key, weight := range list[path.Key].Routes {
			// fmt.Println(list[path.Key].Routes)
			// set to result
			// fmt.Printf("Path(%d, %d) ? result[%d] => %d, wieght: %d\n", path.Key, path.Weight, key, result[key], weight)
			if path.Weight + weight < result[key] {
				result[key] = path.Weight + weight 
				queue = append(queue, Path{key, result[key]})
			// } else if !list[key].Done {
			// 	queue = append(queue, Path{key, result[key]})
			}
		}
		list[path.Key].Done = true
	}
	return result
}
func main() {
	var n int
	fmt.Scanf("%d", &n)
	list := make([]*Vertex, n)
	scanner := bufio.NewScanner(os.Stdin)
	for i := 0; i < n; i++ {
		scanner.Scan()
		elements := strings.Split(scanner.Text(), " ")
		value, _ := strconv.Atoi(elements[0])
		list[i] = NewVertex(value)
		for j := 2; j < len(elements); j += 2 {
			key, _    := strconv.Atoi(elements[j])
			weight, _ := strconv.Atoi(elements[j + 1])
			list[i].SetRoute(key, weight)
		}
	}

	result := ShortestRoutes(list)
	for i := 0; i < len(result); i++ {
		fmt.Printf("%d %d\n", i, result[i]);
	}
	// fmt.Printf("count: %d\n", count)
}

Python: N = int(input())

E = [None] * N
for _ in range(N):
    u, k, *vs = map(int, input().split())
    E[u] = []
    for i in range(k):
        v, c = vs[i*2], vs[i*2+1]
        E[u].append((v, c))

import heapq

vis = [False] * N
inf = 1e9
d = [inf] * N
d[0] = 0
pq = [(0, 0)]
while pq:
    nv, ni = heapq.heappop(pq)
    if nv > d[ni]:
        continue
    d[ni] = nv
    vis[ni] = True
    for v, c in E[ni]:
        nc = d[ni] + c
        if not vis[v] and nc < d[v]:
            heapq.heappush(pq, (nc, v))

for v in range(N):
    print(v, d[v])

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)

Python: # -*- coding: utf-8 -*-
"""
Created on Sat Jul 14 19:11:44 2018

@author: maezawa
"""
infinity = 2*10**9

n = int(input())
adj = [[] for _ in range(n)]

for j in range(n):
    ain = list(map(int, input().split()))
    u = ain[0]
    k = ain[1]
    for i in range(2,2+2*k,2):
        adj[u].append([ain[i],ain[i+1]])
    #print(*adj[u])

color = [0]*n
d = [infinity for _ in range(n)]
p = [0]*n
p[0] = -1
d[0] = 0

def dyk(s):
    cnt = 1
    cur = s
    candidates = set() # remaining nodes
    while True:
        for i, w in adj[cur]:
            if color[i] == 2:
                continue
            if d[i] > d[cur] + w:
                d[i] = d[cur] + w
                color[i] = 1
            candidates.add(i)
        min_d = infinity
        for j in candidates:
            if min_d > d[j]:
                min_node = j
                min_d = d[j]
        candidates.remove(min_node)
        p[min_node] = cur
        color[cur] = 2
        cur = min_node
        cnt += 1
        #print(cur, d)
        #print(candidates)
        if cnt == n:
            break
    return

dyk(0)
for i in range(n):
    print(i, d[i])
    
#print(*p, sep = '\n')