Go: package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

const (
	MAX_N      = 10000
	MAX_WEIGHT = 100000
)

type Edge struct {
	start  int
	end    int
	weight int
}

type ShortestInfo struct {
	edges    []Edge
	shortest int
}

type Neighbor struct {
	node   int
	weight int
}

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

	n, err := nextInt(sc)
	if err != nil {
		panic(err)
	}

	shortestList := make([]ShortestInfo, n)
	for i := 1; i < n; i++ {
		shortestList[i] = ShortestInfo{edges: []Edge{}, shortest: MAX_N*MAX_WEIGHT + 1}
	}

	adjacentMatrix, err := createAdjacentMatrix(n, sc)
	if err != nil {
		panic(err)
	}

	sssp([]int{0}, shortestList, adjacentMatrix)
	for _, v := range shortestList {
		fmt.Printf("%d %d\n", v.getEnd(), v.shortest)
	}
}

func (si ShortestInfo) getEnd() int {
	if len(si.edges) == 0 {
		return 0
	} else {
		return si.edges[len(si.edges)-1].end
	}
}

func createAdjacentMatrix(n int, sc *bufio.Scanner) ([][]Neighbor, error) {
	adjacentMatrix := make([][]Neighbor, n)
	for i := 0; i < n; i++ {
		id, err := nextInt(sc)
		if err != nil {
			return nil, err
		}
		adjacentMatrix[id] = []Neighbor{}
		vertexNum, err := nextInt(sc)
		if err != nil {
			return nil, err
		}
		for j := 0; j < vertexNum; j++ {
			v, err := nextInt(sc)
			if err != nil {
				return nil, err
			}
			c, err := nextInt(sc)
			if err != nil {
				return nil, err
			}
			adjacentMatrix[id] = append(adjacentMatrix[id], Neighbor{v, c})
		}
	}
	return adjacentMatrix, nil
}

func sssp(nodeStack []int, shortestList []ShortestInfo, adjacentMatrix [][]Neighbor) {
	for len(nodeStack) > 0 {
		currentNode := nodeStack[0]
		nodeStack = nodeStack[1:]
		currentShortest := getShortest(currentNode, shortestList)
		adjacents := findAdjacents(currentNode, adjacentMatrix)
		for i := 0; i < len(adjacents); i++ {
			adj := adjacents[i]
			if currentShortest.shortest+adj.weight < getShortest(adj.end, shortestList).shortest {
				setShortest(adj.end, adj, currentShortest, shortestList)
				nodeStack = append(nodeStack, adj.end)
			}
		}
	}
}

func getShortest(node int, shortestList []ShortestInfo) ShortestInfo {
	return shortestList[node]
}

func setShortest(node int, edge Edge, currentShortest ShortestInfo, shortestList []ShortestInfo) {
	newEdges := make([]Edge, len(currentShortest.edges)+1)
	for i := 0; i < len(newEdges)-1; i++ {
		newEdges[i] = currentShortest.edges[i]
	}
	newEdges[len(newEdges)-1] = edge
	shortestInfo := ShortestInfo{edges: newEdges, shortest: currentShortest.shortest + edge.weight}
	shortestList[node] = shortestInfo
}

func findAdjacents(currentNode int, adjacentMatrix [][]Neighbor) []Edge {
	adjacents := adjacentMatrix[currentNode]
	edges := []Edge{}
	for _, neighbor := range adjacents {
		edges = append(edges, Edge{start: currentNode, end: neighbor.node, weight: neighbor.weight})
	}
	return edges
}

func nextInt(sc *bufio.Scanner) (int, error) {
	sc.Scan()
	return strconv.Atoi(sc.Text())
}

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)