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: import argparse
import sys
inf = sys.maxsize
import heapq

def dijkstra_heap(edge_list, node):    
    distance_list = n_node * [inf]
    distance_list[node] = 0
    heap = []
    heapq.heappush(heap, (0, 0))

    while(heap):
        temp_dist, from_node = heapq.heappop(heap)
        if distance_list[from_node] < temp_dist:
            continue
        
        for to_node, cost in edge_list[from_node].items():
            if distance_list[to_node] > distance_list[from_node] + cost:
                distance_list[to_node] = distance_list[from_node] + cost
                heapq.heappush(heap, (distance_list[to_node], to_node))
    
    return distance_list


if __name__ == "__main__":
    parser = argparse.ArgumentParser()
    parser.add_argument('--input', type=str)
    args = parser.parse_args()
    edge_input = []
    if args.input:
        f = open(args.input, 'r')
        n_node = int(f.readline())                
        for _ in range(n_node):            
            edge_input.append(tuple(map(int, f.readline().split()))[2:])
        f.close()
    else:
        n_node = int(input())
        for i in range(n_node):            
            edge_input.append(tuple(map(int, input().split()))[2:])
    
    edge_list = [None] * n_node
    for i in range(n_node):
        edge_list[i] = {}
        for j in range(0, len(edge_input[i]), 2):
            edge_list[i][edge_input[i][j]] = edge_input[i][j+1]

    distance_list = dijkstra_heap(edge_list, 0)

    # # bellman_ford(edge_list, 0)
    # distance_list = dijkstra(edge_list, 0)
    for i, ditance in enumerate(distance_list):
        print(i, distance_list[i])

Python: import sys
input = sys.stdin.readline


def dijkstra_v2(start: int, matrix: list) -> list:
    """dijkstra法: 始点startから各頂点への最短距離を求める
    計算量: O(V^2)
    """
    INF = 10 ** 18
    n = len(matrix)
    used = [False] * n
    dist = [INF] * n
    dist[start] = 0
    while True:
        v = -1
        for u in range(n):
            if not used[u] and (v == -1 or dist[u] < dist[v]):
                v = u
        if v == -1:
            break
        used[v] = True
        for nxt_v in range(n):
            dist[nxt_v] = min(dist[nxt_v], dist[v] + matrix[v][nxt_v])
    return dist
  

n = int(input())
info = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 18

matrix = [[INF] * n for i in range(n)]
for a in range(n):
    matrix[a][a] = 0
    for j in range(1, len(info[a]) // 2):
        b, cost = info[a][slice(2 * j, 2 * (j + 1))]
        matrix[a][b] = cost

dist = dijkstra_v2(0, matrix)
for v, ans in enumerate(dist):
    print(v, ans)

Python: #!/usr/bin/python3
from heapq import heappop, heappush
n = int(input())
inf = 100 * 100000

M = [[] for i in range(n)]

for i in range(n):
    L = list(map(int, input().split()))
    u = L[0]
    k = L[1]
    v = L[2::2]
    c = L[3::2]
    for j in range(k):
        M[u].append((v[j], c[j]))
result = [0] * n
S = set()
V = set(range(n))
S.add(0)
d = []
for m in M[0]:
    heappush(d, (m[1], m[0]))
T = V - S

while len(T) != 0:
    c, v = heappop(d)
    while v in S:
        c, v = heappop(d)
    result[v] = c
    S.add(v)
    T.remove(v)
    for m in M[v]:
        if m[0] in T:
            heappush(d, (result[v] + m[1], m[0]))

for i, v in enumerate(result):
    print(i, v)

Python: n = int(input())
edgeList = []
for i in range(n):
    a = list(map(int, input().split()))
    for j in range(a[1]):
        edgeList.append([a[2*j+3], i, a[2*j+2]])
 
 
rootList = [-1 for i in range(n)]
parent = [0 for i in range(n)]
lenList = [float("inf") for i in range(n)]
lenList[0] = 0
def getRoot(x):
    r = rootList[x]
    if r < 0:
        rootList[x] = x
    elif r != x:
        rootList[x] = getRoot(r)
    return rootList[x]
 
flag = True
while flag:
    flag = False
    edgeList.sort(key=lambda x: (x[0] + lenList[x[1]]))
    for e in edgeList:    # weight:e[0], e[1]->e[2]
        if e[2] == 0:
            continue
        x = getRoot(e[1])
        y = getRoot(e[2])
        if x == 0 != y:
            parent[e[2]] = e[1]
            lenList[e[2]] = lenList[e[1]] + e[0]
            rootList[y] = 0
            flag = True
            break
 
for i, j in zip(range(n), lenList):
    print(i, j)

Python: n = int(input())
g = []
for i in range(n):
    line = list(map(int, input().split()))
    k = line[1]
    c = [100001] * n
    for j in range(k):
        v = line[2 + 2 * j]
        c[v] = line[3 + 2 * j]
    g.append(c)

distance = [100001] * n
distance[0] = 0
visited = [False] * n
current = 0

while not all(visited):
    min_i = 0
    min_d = 100001
    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]
    visited[current] = True
    current = min_i

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

Python: import sys
import heapq
def dijkstra(G,s):
    n= len(G)
    dist = [float("inf") for i in range(n)]
    vis =  [-1 for i in range(n)]
    l = [(0,s)]
    dist[s]=0
    heapq.heapify(l)
    while len(l):
        d,u = heapq.heappop(l)
        if(vis[u]==1):
            continue
        else:
            vis[u]=1
            for i in G[u]:
                if(d+i[0]<dist[i[1]]):
                   dist[i[1]]= d+i[0]
                   heapq.heappush(l,(d+i[0],i[1]))
    return dist
        
        
def main():
    casos = int(sys.stdin.readline().strip())
    for k in range(casos):
        line = [int(x) for x in sys.stdin.readline().strip().split()]
        u = line[0]
        E = line[1]
        maxi = 0
        for i in range(2,len(line),2):
            maxi= max(maxi,line[i])
        maxi = max(maxi,u)
        G =[[] for i in range(maxi+1)]
        for j in range(2,len(line)-1,2):
           
            G[u].append((line[j+1],line[j]))
            G[line[j]].append((line[j+1],u))
        
        r=dijkstra(G,0)
        print(r)
        print(u,r[u])
        
        

    
main()