Go: package main

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

var scanner = bufio.NewScanner(os.Stdin)

func nextString() string {
	scanner.Scan()
	return scanner.Text()
}

func nextInt() int {
	n, err := strconv.Atoi(nextString())
	if err != nil {
		fmt.Printf("strconv.Atoi failed: %v\n", err)
	}
	return n
}

var infty = 1000000000

type DirectedGraphNodeID int

type DirectedGraphNode struct {
	key         DirectedGraphNodeID
	adjacents   []*DirectedGraphNode
	costs       []int
	distance    int
	predecessor *DirectedGraphNode
}

func newDirectedGraph(nNodes int) *DirectedGraph {
	graph := DirectedGraph{}
	graph.nodes = make([]*DirectedGraphNode, nNodes)
	for i := 0; i < nNodes; i++ {
		node := DirectedGraphNode{}
		node.key = DirectedGraphNodeID(i)
		node.distance = infty
		graph.nodes[i] = &node
	}
	return &graph
}

type DirectedGraph struct {
	nodes []*DirectedGraphNode
}

func (g *DirectedGraph) setAdjacency(i, j DirectedGraphNodeID, cost int) {
	g.nodes[i].adjacents = append(g.nodes[i].adjacents, g.nodes[j])
	g.nodes[i].costs = append(g.nodes[i].costs, cost)
}

func (g *DirectedGraph) print() {
	for i := 0; i < len(g.nodes); i++ {
		node := g.nodes[i]
		key := node.key
		strings := []string{strconv.Itoa(int(key)), strconv.Itoa(node.distance)}
		for j := 0; j < len(node.adjacents); j++ {
			nodeJ := fmt.Sprintf("(%v, %v)", node.adjacents[j].key, node.costs[j])
			strings = append(strings, nodeJ)
		}
		fmt.Printf("%v\n", strings)
	}
}

func (g *DirectedGraph) relaxEdge(l, r *DirectedGraphNode, w int) {
	if r.distance > l.distance+w {
		// fmt.Printf("%v -> %v, %v\n", l.key, r.key, l.distance+w)
		r.distance = l.distance + w
		r.predecessor = l
	}
}

func main() {
	scanner.Split(bufio.ScanWords)

	nNodes := nextInt()
	graph := newDirectedGraph(nNodes)

	for i := 0; i < nNodes; i++ {
		iNode := DirectedGraphNodeID(nextInt())
		nAdjacent := nextInt()
		for j := 0; j < nAdjacent; j++ {
			jNode := DirectedGraphNodeID(nextInt())
			cost := nextInt()
			graph.setAdjacency(iNode, jNode, cost)
		}
	}

	graph.nodes[0].distance = 0
	for iNode := 0; iNode < nNodes; iNode++ {
		for iLeft := 0; iLeft < len(graph.nodes); iLeft++ {
			nodeLeft := graph.nodes[iLeft]
			for iRight := 0; iRight < len(nodeLeft.adjacents); iRight++ {
				nodeRight := nodeLeft.adjacents[iRight]
				cost := nodeLeft.costs[iRight]
				graph.relaxEdge(nodeLeft, nodeRight, cost)
			}
		}
	}

	// graph.print()

	for iNode := 0; iNode < len(graph.nodes); iNode++ {
		node := graph.nodes[iNode]
		fmt.Println(node.key, node.distance)
	}
}

Python: def dijkstra(n,s):
    inf=float("inf")
    color=["white" for i in range(n)]
    D=[inf for i in range(n)]
    P=[0 for i in range(n)]
    M=[[inf for i in range(n)] for j in range(n)]

    for i in range(n):
        weight=list(map(int,input().split()))[2:]
        for j in range(len(weight)//2):
            M[i][weight[2*j]]=weight[2*j+1]

    D[s]=0
    P[s]=-1

    while 1:
        cost,u=inf,0
        for i in range(n):
            if color[i]!="black" and D[i]<cost:
                cost=D[i]
                u=i

        if cost==inf:break

        color[u]="black"

        for i in range(n):
            if color[i]!="black" and M[u][i]!=inf:
                if D[u]+M[u][i]<D[i]:
                    D[i]=D[u]+M[u][i]
                    color[i]="gray"
                    P[i]=u

    return D


n=int(input())
distant=dijkstra(n,0)
for i in range(n):
    print(i,distant[i])

Python: def dijkstra():
    d[0] = 0
    color[0] = GRAY

    while True:
        minv = INF
        u = -1
        for i in range(N):
            if minv > d[i] and color[i] != BLACK:
                u = i
                minv = d[i]
        if u == -1:
            break
        color[u] = BLACK
        for i in range(N):
            if color[i] != BLACK and M[u][i] != INF:
                if d[i] > d[u] + M[u][i]:
                    d[i] = d[u] + M[u][i]
                    color[i] = GRAY

INF = 10 ** 18
WHITH = 0
GRAY = 1
BLACK = 2
N = int(input())
M = [[INF for _ in range(N)] for _ in range(N)]
d = [INF] * N
color = [WHITH] * N

for i in range(N):
    lst = list(map(int, input().split()))
    for j in range(lst[1]):
        M[lst[0]][lst[2 + (j * 2)]] = lst[3 + (j * 2)]

dijkstra()
for i in range(N):
    v = d[i]
    if v == INF:
        v = -1
    print(i, v)

Python: #!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	single_source_shortest_path
# CreatedDate:  2020-06-08 21:54:58 +0900
# LastModified: 2020-06-08 22:28:47 +0900
#


import os
import sys
from collections import deque
#import numpy as np
#import pandas as pd


def main():
    n = int(input())
    graph = [[] for _ in range(n)]
    for _ in range(n):
        line = list(map(int,input().split()))
        u,k = line[0],line[1]
        path = line[2:]
        for i in range(0,2*k,2):
            graph[u].append([path[i+1],path[i]])
    
#    print(graph)
    s=0
    distance=[-1]*n
    Q = deque([s])
    distance[0]=0
    

    while Q:
        u = Q.popleft()
        for dis,v in graph[u]:
            if distance[v]==-1:
                distance[v]=distance[u]+dis
                Q.append(v)

            if distance[v]>distance[u]+dis:
                distance[v]=distance[u]+dis
                Q.append(v)
            


    for i,dis in enumerate(distance):
        print(i,dis)


if __name__ == "__main__":
    main()

Python: INF = 100000 * 100

def dijkstra(s: int) -> None:
	d[s] = 0	
	while True:
		mincost = INF
		for i in range(n):
			if color[i] != "BLACK" and d[i] < mincost:
				mincost = d[i]
				u = i
		if mincost == INF:
			break
		color[u] = "BLACK"
		for v in range(n):
			if color[v] != "BLACK" and M[u][v] != None:
				if d[u] + M[u][v] < d[v]:
					d[v] = d[u] + M[u][v]
					pi[v] = u
					color[v] = "GRAY"


if __name__ == "__main__":
	n = int(input())
	G = []
	M = [[None for _ in range(n)] for _ in range(n)]
	color = ["WHITE" for _ in range(n)]
	d = [INF for _ in range(n)]
	pi = [None for _ in range(n)]

	for _ in range(n):
		l = list(map(int, input().split()))
		u = l[0]
		k = l[1]
		for i in range(k):
			v = l[2 * (i + 1)]
			c = l[2 * (i + 1) + 1]
			M[u][v] = c
	dijkstra(0)
	for v in range(n):
		print(f"{v} {d[v]}")

Python: import sys

def dijkstra(v_count: int, edges: list, start: int,
             *, adj_matrix: bool = False, unreachable=float("inf")) -> list:
    """ ダイクストラ法
    :param v_count: 頂点数
    :param edges: 辺のリスト(隣接リストor隣接行列)
    :param start: スタートする頂点
    :param adj_matrix: edgesに渡したリストが隣接行列ならTrue
    :param unreachable: 到達不能を表すコスト値
                        隣接行列の辺の有無の判定および返すリストの初期値に使用
    """
    from heapq import heappush, heappop

    vertices = [unreachable] * v_count
    vertices[start] = 0
    q, rem = [(0, start)], v_count - 1

    while q and rem:
        cost, v = heappop(q)
        if vertices[v] < cost:
            continue
        rem -= 1

        dests = (filter(lambda x: x[1] != unreachable, enumerate(edges[v]))
                 if adj_matrix else edges[v])

        for dest, _cost in dests:
            newcost = cost + _cost
            if vertices[dest] > newcost:
                vertices[dest] = newcost
                heappush(q, (newcost, dest))

    return vertices

n = int(input())
inf = float("inf")
edges = [[inf]*n for _ in [0]*n]
for a in (tuple(map(int, l.split())) for l in sys.stdin):
    _from = a[0]
    for to, cost in zip(a[2::2], a[3::2]):
        edges[_from][to] = cost
vertices = dijkstra(n, edges, 0, adj_matrix=True)
for i, n in enumerate(vertices):
    print(i, n)