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: 
def dijkstra():
    global n, color, M, d, p

    min_value = 1000000
    d[0] = 0
    color[0] = 'GRAY'

    while True:
        min_value = 1000000
        u = -1

        for i in range(n):
            if min_value > d[i] and color[i] != 'BLACK':
                u = i
                min_value = d[i]

        if u == -1:
            break

        color[u] = 'BLACK'

        for v in range(n):
            if color[v] != 'BLACK' and M[u][v] != 1000000:
                if d[v] > d[u] + M[u][v]:
                    d[v] = d[u] + M[u][v]
                    color[v] = 'GRAY'

    for i in range(n):
        if d[i] == 1000000:
            d[i] = -1

        print('{} {}'.format(i, d[i]))


n = int(input())

color = ['WHITE'] * n
M = [[1000000 for i in range(n)] for j in range(n)]
d = [1000000] * n  # 重みが最小の辺の重み
p = [-1] * n  # MSTにおけるp[v]の親（どこから来たか？？）

for i in range(n):
    _ = list(map(int, input().split()))
    u = _[0]
    degree = _[1]

    for j in range(degree):
        v = _[j*2+2]
        w = _[j*2+3]
        M[u][v] = w
# print(M)

dijkstra()

Python: def dijkstra(n):
    inf = 10 ** 6 + 1
    dist = [0] + [inf] * (n - 1)
    visited = [False] * n

    while not all(visited):
        dmin = inf
        for i, (d, v) in enumerate(zip(dist, visited)):
            if dmin > d and not v:
                dmin, u = d, i
        visited[u] = True
        for (v, c) in edge[u]:
            if dist[v] > dist[u] + c:
                dist[v] = dist[u] + c
    return dist

n = int(input())
edge = [[]] * n
for _ in range(n):
    l = list(map(int, input().split()))
    edge[l[0]] = (e for e in zip(l[2::2], l[3::2]))
for i, c in enumerate(dijkstra(n)):
    print(i, c)

Python: n = int(input())
G = [[] for i in range(n)]
for ni in range(n):
    u, k, *tmp = [int(i) for i in input().split()]
    for ki in range(k):
        G[ni].append(tmp[:2])
        del tmp[:2]

INF = 100*100000
D = [INF for i in range(n)]
D[0] = 0
C = [0 for i in range(n)]
while 0 in C:
    U = [INF if C[i] == 1 else D[i] for i in range(n)]
    u = U.index(min(U))

    for i in range(len(G[u])):
        v = G[u][i][0]
        if D[u] + G[u][i][1] < D[v]:
            D[v] = D[u] + G[u][i][1]
    C[u] = 1

for ni in range(n):
    print(ni, D[ni])

Python: import sys
import heapq
n = int(input())
V = [[int(i) for i in input().split()] for _ in range(n)]
dis = [sys.maxsize for _ in range(n)]
dis[0] = 0
h = []
for i in range(n):
    heapq.heappush(h,(dis[i],i))
while(len(h)>0):
    node = heapq.heappop(h)
    tmp = node[1]
    for i in range(V[tmp][1]):
        ind = V[tmp][2*i+2]
        cos = V[tmp][2*i+3]
        if cos + dis[tmp] < dis[ind]:
            dis[ind] = cos + dis[tmp]
            heapq.heappush(h,(dis[ind],ind))
for i,j in enumerate(dis):
    print(i,j)

Python: import heapq


def dijkstra(start_v, G):
    n = len(G)
    dist = [0 if i == start_v else float("inf") for i in range(n)]

    que = []
    heapq.heappush(que, (0, start_v))

    while que:
        cur_d, cur_v = heapq.heappop(que)
        if dist[cur_v] < cur_d:
            continue
        for adj in G[cur_v]:
            nxt_v, cost = adj
            if dist[cur_v] + cost < dist[nxt_v]:
                dist[nxt_v] = dist[cur_v] + cost
                heapq.heappush(que, (dist[nxt_v], nxt_v))

    return dist


def main():
    n = int(input())
    g = [[] for _ in range(n)]

    for i in range(n):
        data = [int(x) for x in input().split()]
        u, k = data[0], data[1]
        vc = data[2:]
        for j in range(k):
            v, c = vc[2 * j], vc[2 * j + 1]
            g[u].append((v, c))

    dist = dijkstra(0, g)

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


main()

Python: """Shortest Path"""

import sys
import os
import pprint

#fd = os.open('ALDS1_12_B.txt', os.O_RDONLY)
#os.dup2(fd, sys.stdin.fileno())

level = True
def debug(v):
    if level:
        print(v)

n = int(input())
INF = 100001
W = [[INF for j in range(n)] for i in range(n)]

for _ in range(n):
    l = list(map(int, input().split()))
    node_index = l[0]
    num = l[1]
    data = l[2:]
    for i in range(num):
        node = data[i*2]
        weight = data[i*2+1]
        W[node_index][node] = weight

d = [INF] * n
visited = [False] * n
parent = [None] * n

# root
d[0] = 0

while True:
    min_dist = INF
    min_index = None
    for i in range(n):
        if not visited[i] and d[i] < min_dist:
            min_dist = d[i]
            min_index = i

    if min_index is None:
        break

    # accept
    visited[min_index] = True

    for i in range(n):
        if not visited[i] and d[i] > d[min_index] + W[min_index][i]:
            d[i] = d[min_index] + W[min_index][i]
            parent[i] = min_index
for i in range(len(d)):
    s = '{} {}'.format(i, d[i])
    print(s)

Python: import heapq

n = int(input())
edges = [None] * n
for _ in range(n):
    l = list(map(int, input().split()))
    edges[l[0]] = set((c, j) for j, c in (l[i:i + 2] for i in range(2, l[1] * 2 + 2, 2)))

min_costs = [0] * n
visited = [False] * n
visited[0] = True
queue = list(edges[0])
heapq.heapify(queue)

while queue:
    total_cost, vertex = heapq.heappop(queue)
    if visited[vertex]:
        continue
    visited[vertex] = True
    min_costs[vertex] = total_cost
    for cost, vertex2 in edges[vertex]:
        if not visited[vertex2]:
            heapq.heappush(queue, (total_cost + cost, vertex2))

for r in enumerate(min_costs):
    print(*r)