Go: package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func main() {
	fp := os.Stdin
	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(os.Stdout)

	n := getNextInt(scanner)

	g := makeGraph(n)
	for i := 0; i < n; i++ {
		u := getNextInt(scanner)
		k := getNextInt(scanner)
		for ii := 0; ii < k; ii++ {
			v := getNextInt(scanner)
			c := getNextInt(scanner)
			g[u][v] = c
		}
	}

	ans := make([]int, n)
	im := make(IntMap, 1)
	im.increment(0)
	for len(im) < n {
		min := 1 << 30
		x := -1
		for u := range im {
			for v := 0; v < n; v++ {
				if im.get(v) != 0 {
					continue
				}
				if min > ans[u]+g[u][v] {
					min = ans[u] + g[u][v]
					x = v
				}
			}
		}
		im.increment(x)
		ans[x] = min
	}

	for i := 0; i < n; i++ {
		fmt.Fprintln(writer, fmt.Sprintf("%d %d", i, ans[i]))
	}
	writer.Flush()
}

func makeGraph(n int) [][]int {
	g := make([][]int, n)
	for i := 0; i < n; i++ {
		g[i] = make([]int, n)
		for ii := 0; ii < n; ii++ {
			g[i][ii] = 1 << 30
		}
	}

	return g
}

// IntMap ...
type IntMap map[int]int

func (m IntMap) get(key int) int {
	if _, ok := m[key]; ok {
		return m[key]
	}
	return 0
}
func (m IntMap) increment(key int) {
	if _, ok := m[key]; ok == false {
		m[key] = 0
	}
	m[key]++
}

Python: # coding: utf-8

import heapq


class Dijkstra:

    """
    Dijkstra's algorithm: find the shortest path from a vertex
    Complexity: O(E + log(V))
    used in GRL1A(AOJ)
    """

    def __init__(self, V, G, INF=float("inf")):

        """
        V: the number of vertexes
        E: adjacency list (all edge in G must be 0 or positive)
        INF: Infinity distance
        """
        self.V = V
        self.G = G
        self.INF = INF
        self.distance, self.prev = list(), list()


    def dijkstra(self, start):

        Q = list()
        self.distance = [self.INF for _ in range(self.V)]
        self.prev = [-1 for _ in range(self.V)]

        self.distance[start] = 0
        heapq.heappush(Q, (0, start))

        while len(Q) > 0:
            dist, from_v = heapq.heappop(Q)
            if self.distance[from_v] < dist:
                continue
            for to_v, nxt_dist in self.G[from_v]:
                if self.distance[from_v] + nxt_dist >= self.distance[to_v]:
                    continue
                self.distance[to_v] = self.distance[from_v] + nxt_dist
                heapq.heappush(Q, (self.distance[to_v], to_v))
                self.prev[to_v] = from_v
        
        return self.distance


    def get_path(self, goal):

        path = [goal]
        while self.prev[goal] != -1:
            path.append(prev[goal])
            goal = self.prev[end]

        return path[::-1]


if __name__ == "__main__":
    
    n = int(input())
    g = [[] for _ in range(n)]
    for _ in range(n):
        v, _, *e = map(int, input().split())
        for u, d in zip(e[::2], e[1::2]):
            g[v].append((u, d))

    dist = Dijkstra(n, g).dijkstra(0)
    for i, d in enumerate(dist):
        print(i, d)

Python: from enum import Enum


class Sssp(object):
    """ single source shortest path """
    INFINITY = 999999999
    class Status(Enum):
        """ ?????????????¨??????¶??? """
        white = 1  # ????¨????
        gray = 2  # ?¨???????
        black = 3  #?¨???????

    def __init__(self, data):
        num_of_nodes = len(data)
        self.color = [Sssp.Status.white] * num_of_nodes  # ????????????????¨??????¶???
        self.M = [[Sssp.INFINITY] * num_of_nodes for _ in range(num_of_nodes)]
        self._make_matrix(data)  # data????????????????????£??\??????(?????\?¶???¨???????????????????????§????????????)
        self.d = [Sssp.INFINITY] * num_of_nodes
        self.p = [-1] * num_of_nodes  # ????????????????????????????¨??????????

    def _make_matrix(self, data):
        for d in data:
            my_id = d[0]
            d = d[2:]
            while len(d) > 1:
                to_node, cost = d[0], d[1]
                self.M[my_id][to_node] = cost
                d = d[2:]

    def dijkstra(self, start):
        self.d[start] = 0
        self.p[start] = -1

        while True:
            mincost = Sssp.INFINITY
            for i in range(len(self.d)):
                if self.color[i] != Sssp.Status.black and self.d[i] < mincost:
                    mincost = self.d[i]
                    u = i

            if mincost == Sssp.INFINITY:
                break

            self.color[u] = Sssp.Status.black

            for v in range(len(self.d)):
                if self.color[v] != Sssp.Status.black and self.M[u][v] != Sssp.INFINITY:
                    if self.d[u] + self.M[u][v] < self.d[v]:
                        self.d[v] = self.d[u] + self.M[u][v]
                        self.p[v] = u
                        self.color[v] = Sssp.Status.gray


if __name__ == '__main__':
    # ??????????????\???
    num = int(input())
    data = []
    for i in range(num):
        data.append(list(map(int, input().split(' '))))

    # ???????????¢?´¢
    s = Sssp(data)
    s.dijkstra(0)

    # ???????????¨???
    for i in range(num):
        print('{0} {1}'.format(i, s.d[i]))

Python: n=int(input())
inf=10**15;d=[inf]*n;d[0]=0
node=[[]for _ in range(n)]
for i in range(n):
	x=list(map(int,input().split()))
	for j in range(x[1]):
		node[i].append((x[j*2+2],x[j*2+3]))
dis=[[inf]*n for _ in range(n)]
for i in range(n):
	dis[i][i]=0
for i in range(n):
	for x in node[i]:
		dis[i][x[0]]=x[1]
s=[False]*n
while True:
	min_cost=inf
	for i in range(n):
		if s[i]==0 and d[i]<min_cost:
			min_cost=d[i]
			u=i
	if min_cost==inf:
		break
	s[u]=True
	for i in range(n):
		if s[i]==False and dis[u][i]!=inf:
			if d[u]+dis[u][i]<d[i]:
				d[i]=d[u]+dis[u][i]		
for i in range(n):
	print(i,d[i])

Python: n = int(input())
from collections import defaultdict
G = defaultdict(list)
for i in range(n):
    i = [int(i) for i in input().split()]
    k = i[1]
    G[i[0]] = list(zip(i[2::2],i[3::2]))

def mind(Q, d):
    c = float('inf')
    ret = 0
    for i, j in enumerate(d):
        if c > j and i in Q:
            c = j
            ret = i
    return ret

def dijkstra(G):
    d = [0] + [float('inf')] * (n - 1)
    Q = set(range(n))
    while len(Q) != 0:
        u = mind(Q, d)
        print(u)
        Q = Q - set([u])
        for v, c in G[u]:
            if d[v] > d[u] + c:
                d[v] = d[u] + c
    return d

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