Go: package main

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

const NIL = -1

type Node struct {
	id     int
	weight int
}

func init() {
	sc.Split(bufio.ScanWords)
}

type NodeHeap []Node

func (h NodeHeap) Len() int           { return len(h) }
func (h NodeHeap) Less(i, j int) bool { return h[i].weight < h[j].weight }
func (h NodeHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *NodeHeap) Push(x interface{}) {
	*h = append(*h, x.(Node))
}

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

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	num, _ := strconv.Atoi(scanString())
	return num
}

func scanString() string {
	sc.Scan()
	return sc.Text()
}

func init() {
	sc.Split(bufio.ScanWords)
}

func main() {
	n := scanInt()

	list := make([][]int, n)
	weight := make([]int, n)
	for i := range list {
		list[i] = make([]int, n)
		weight[i] = NIL
		for j := range list[i] {
			list[i][j] = NIL
		}
	}

	for i := 0; i < n; i++ {
		u := scanInt()
		k := scanInt()
		for j := 0; j < k; j++ {
			v := scanInt()
			w := scanInt()
			list[u][v] = w
		}
	}

	start := Node{id: 0, weight: 0}
	h := &NodeHeap{start}
	heap.Init(h)

	for h.Len() > 0 {
		node := heap.Pop(h).(Node)
		if weight[node.id] != NIL {
			continue
		}
		weight[node.id] = node.weight

		for i, w := range list[node.id] {
			if w == NIL {
				continue
			}
			heap.Push(h, Node{id: i, weight: w + node.weight})
		}
	}

	w := bufio.NewWriter(os.Stdout)
	for i := 0; i < n; i++ {
		fmt.Fprint(w, i)
		fmt.Fprint(w, " ")
		fmt.Fprint(w, weight[i])
		fmt.Fprintln(w)
	}
	w.Flush()
}

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)