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: INFTY = 1 << 21
WHITE = 0
GRAY = 1
BLACK = 2
 
n = int(input())
M = [list(map(int, input().split())) for i in range(n)]
 
d = [INFTY for i in range(n)]
color = [WHITE for i in range(n)]
 
for i in range(n):
    u = int(input())
    k = int(input())
    for j in range(k):
        v = int(input())
        c = int(input())
        M[u][v] = c
        
def dijkstra():
    global M, d, color
    d[0] = 0
    color[0] = GRAY
    while(1):
        minv = INFTY
        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 v in range(n):
            if (color[v] != BLACK and M[u][v] != INFTY):
                if (d[v] > d[u] + M[u][v]):
                    d[v] = d[u] + M[u][v]
                    color[v] = GRAY
    for i in range(n):
        print(str(i), (-1 if d[i] == INFTY else str(d[i])))
dijkstra()

Python: import queue

INFTY=1<<21

#ダイクストラ法
def dijkstra(n,EdgeMatrix):

    NodeList=queue.PriorityQueue() #探索対象の頂点
    Distance=[INFTY]*n #頂点0からの最短経路
    used=[False]*n #頂点の使用情報

    Distance[0]=0 #0から0までの距離は0
    used[0]=True #0から探索を始める
    LastNode=0 #最新の頂点
    count=1 #つないだ頂点の数

    while count<n:
        for i in range(n):
            #探索していない頂点へ距離の短い辺があればキューに追加
            if EdgeMatrix[LastNode][i]!=INFTY and used[i]==False:
                if Distance[i]>Distance[LastNode]+EdgeMatrix[LastNode][i]:
                    Distance[i]=Distance[LastNode]+EdgeMatrix[LastNode][i]
                    NodeList.put([Distance[i],i])

        #最も近い探索していない頂点
        while True:
            minNode=NodeList.get()
            if used[minNode[1]]==False:
                break

        LastNode=minNode[1] #最新の頂点を更新
        used[minNode[1]]=True #頂点の使用情報を更新
        count+=1 #つないだ頂点の数を更新

    return Distance

#入力
n=int(input())

#辺の隣接行列
EdgeMatrix=[[INFTY]*n for i in range(n)]
for i in range(n):
    l=(list(map(int,input().split())))
    for j in range(l[1]):
        EdgeMatrix[l[0]][l[2*j+2]]=l[2*j+3]

#頂点0からの最短経路
Distance=dijkstra(n,EdgeMatrix)

for node,distance in enumerate(Distance):
    print(node,distance)

Python: import sys
readline = sys.stdin.readline
from heapq import heapify, heappush, heappop
INF = float("inf")
def MAIN():
    n = int(input())
    adj = [[]] * n
    for _ in range(0, n):
        U = list(map(int, input().split()))
        adj[U[0]] = zip(U[2::2], U[3::2])
    def dijkstra():
        d = [0] + [INF] * (n - 1)
        hq = [(0, 0)]
        while hq:
            u = heappop(hq)[1]
            for v, c in adj[u]:
                alt = d[u] + c
                if d[v] > alt:
                    d[v] = alt
                    heappush(hq, (alt, v))
        print("\n".join(f"{i} {c}" for i, c in enumerate(d)))
    dijkstra()
MAIN()

Python: #coding:utf-8
def Dijkestra(G,n):
    d=[100000000000]*n
    pi=[None]*n
    d[0]=0
    C=[]
    for i in range(n):
        C.append(i)
    
    while len(C)!=0:
        u=C[0]
        for i in range(1,len(C)):
            if d[u]>d[i]:
                u=i
        C.remove(u)
        for i in range(len(G[u])):
            if G[u][i]==-1:
                continue
            elif d[i]>d[u]+G[u][i]:
                d[i]=d[u]+G[u][i]
                pi[i]=u
                        
    for i in range(n):
        print(i,d[i])
    

if __name__=="__main__":
    n=int(input())
    G=[]
    for i in range(n):
        a=[]
        ele=list(map(int,input().split()))
        k=ele[1]
        t=ele[2:]
        v=c=[]
        for j in range(k):
            v=v+[t[2*j]]
            c=c+[t[2*j+1]]
        for j in range(n):
            if j in v:
                a.append(c[v.index(j)])
            else:
                a.append(-1)
        G.append(a)
    Dijkestra(G,n)

Python: n = int(input())
E = [[] for i in range(n)]#[[]]*nだと同一アドレスの単一リストがコピーされる
lrg = 10**8
for i in range(n):
    inpt = list(map(int, input().split( )))
    for j in range(inpt[1]):
        E[inpt[0]].append(inpt[2*j+2:2*j+4])
    #print(inpt[0],E[inpt[0]],*inpt)

D = [lrg]*n
D[0] = 0

G =[0]

Prev = [-1]*n
cnt=0
while cnt < n:#len(D)<nでは制御できていない,Dは距離,Gは到達リスト
    for v in G:
        for [u,c] in E[v]:
            if D[u]>D[v]+c:
                #print("replaced")
                D[u] = D[v]+c
                Prev[u]=v
            if u not in G:
                G.append(u)
                #print("append",u)
    cnt+=1            
for v in G:
    for [u,c] in E[v]:
        if D[u]>D[v]+c:
            D[u] = D[v]+c
            Prev[u]=v
            
for i in range(n):
    print(i,D[i])

Python: 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)