Go: // ダイクストラのアルゴリズム
package main

import (
	"bufio"
	"fmt"
	"log"
	"math"
	"os"
	"strconv"
	"strings"
)

type color int

const (
	white color = iota // 未訪問
	mst                // MSTとして確定
)

// 頂点
type node struct {
	num     int         // 頂点の番号
	weights map[int]int // 重みMAP
	parent  *node       // MSTへの重み最小の親
	sum     int         // 始点からの距離
	color   color
}

func (p *node) getMinToMst() int {
	if p.parent == nil {
		return math.MaxInt32
	}
	return p.weights[p.parent.num]
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	n := eGetInt(scanner)

	nodes := make([]*node, n)
	for i := 0; i < n; i++ {
		weights := eAtoi((strings.Fields(eGetline(scanner))))
		v := &node{weights[0], make(map[int]int, weights[1]), nil, 0, white}
		for j := 0; j < weights[1]; j++ {
			k := weights[j*2+2] // 相手の頂点名
			w := weights[j*2+3] // 重み
			v.weights[k] = w
		}
		nodes[i] = v
	}

	// 初回はnode[0]がMSTに入るように
	nodes[0].parent = nodes[0]

	for { // 全部チェックするまで

		// どの頂点を新たにMSTに取り込むか

		var minNode *node
		min := math.MaxInt32
		for _, v := range nodes {
			if v.color == mst {
				continue
			}
			if v.getMinToMst() < min {
				min = v.getMinToMst()
				minNode = v
			}
		}
		if minNode == nil {
			// すべて完了している.
			break
		}

		// MSTに追加する頂点決定
		minNode.color = mst
		// 自分の親の合計値と合算する
		minNode.sum = minNode.parent.sum + min

		// MSTに属していない頂点それぞれについて,MSTとの最小の重みの距離を加算
		for _, v := range nodes {
			if v.color == mst {
				continue
			}
			w, ok := v.weights[minNode.num]
			if !ok {
				// minNodeと接してない
				continue
			}

			if w < v.getMinToMst() {
				// minNodeへの距離がもっとも重みが少ないので親を変更
				v.parent = minNode
			}
		}
	}

	for i, v := range nodes {
		fmt.Printf("%d %d\n", i, v.sum)
	}
}

func eGetInt(scanner *bufio.Scanner) int {
	t := eAtoi(strings.Fields(eGetline(scanner)))
	return t[0]
}

func eGetline(p *bufio.Scanner) string {
	if !p.Scan() {
		if err := p.Err(); err != nil {
			log.Fatal(err.Error())
		}
		return ""
	}
	return p.Text()
}

func eAtoi(s []string) []int {
	ints := make([]int, len(s))
	var err error
	for i, e := range s {
		ints[i], err = strconv.Atoi(e)
		if err != nil {
			log.Fatal(err.Error())
		}
	}
	return ints
}

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)

Python: import sys

INFTY=sys.maxsize
WHITE=0
GRAY=1
BLACK=2

def readinput():
    n=int(input())
    nMap=[]
    for _ in range(n):
        nMap.append([INFTY]*n)

    for _i in range(n):
        l=list(map(int,input().split()))
        i=l[0]
        for jj in range(l[1]):
            j=l[2+jj*2]
            w=l[2+jj*2+1]
            nMap[i][j]=w
    return n, nMap

color=[]
d=[]
p=[]

def dijkstra(s,n,nMap):
    global color
    global d
    global p
    
    color=[WHITE]*n
    d=[INFTY]*n
    p=[-1]*n

    d[s]=0
    p[s]=-1

    while True:
        mincost=INFTY
        for i in range(n):
            if color[i]!=BLACK and d[i] < mincost:
                mincost=d[i]
                u=i
        if mincost==INFTY:
            break
        color[u]=BLACK

        for v in range(n):
            if color[v]!=BLACK and nMap[u][v]!=INFTY:
                if d[u]+nMap[u][v] < d[v]:
                    d[v]=d[u]+nMap[u][v]
                    p[v]=u
                    color[v]=GRAY

def main(n,nMap):

    dijkstra(0,n,nMap)
    for i in range(n):
        print('{} {}'.format(i,d[i]))

if __name__=='__main__':
    n,nMap=readinput()
    main(n,nMap)

Python: # -*- coding: utf-8 -*-

import sys
from heapq import heappush, heappop

sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
INF=float('inf')

# ダイクストラ(頂点数, 隣接リスト(0-indexed), 始点)
def dijkstra(N: int, nodes: list, src: int) -> list:
    # 頂点[ある始点からの最短距離]
    # (経路自体を知りたい時はここに前の頂点も持たせる)
    res = [float('inf')] * N
    # スタート位置
    que = [(0, src)]
    res[src] = 0
    # キューが空になるまで
    while len(que) != 0:
        # srcからの距離, 現在のノード
        dist, cur = heappop(que)
        # 出発ノードcurの到着ノードでループ
        for nxt, cost in nodes[cur]:
            # 今回の経路のが短い時
            if res[cur] + cost < res[nxt]:
                res[nxt] = res[cur] + cost
                # 現在の移動距離をキューの優先度として、早い方から先に処理するようにする
                heappush(que, (res[nxt], nxt))
    # ノードsrcからの最短距離リストを返却
    return res

N=INT()
nodes=[[] for i in range(N)]
for i in range(N):
    l=LIST()
    u=l[0]
    k=l[1]
    l=l[2:]
    for j in range(0, k*2, 2):
        nodes[u].append((l[j], l[j+1]))

ans=dijkstra(N, nodes, 0)
for i in range(N):
    print(i, ans[i])

Python: # https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/12/ALDS1_12_B
# プリムのアルゴリズムと似ているが、求めているものが異なる(MSTの経路は必ずしも任意の点と点をつなぐ最小経路とはならない)。
# 次手の候補となるリストDの更新の仕方がprimとは異なる

INF = 10**6 + 1

# load datas
N = int(input())
M = [[INF] * N for _ in range(N)]  # 隣接行列
for _ in range(N):
    tmp = list(map(int, input().split()))
    if tmp[1] != 0:
        node = tmp[0]
        for i, t in enumerate(tmp[2:]):
            if i % 2 == 0:
                idx = t
            else:
                M[node][idx] = t


def dijkstra(adj_mat: list, s: int):
    Color = [0] * N  # 0:未訪問 1:訪問経験あり 2:訪問済み(そこまでの最短経路は確定済み)
    D = [INF] * N  # 本のdと同じ 始点からの距離を記録する
    P = [None] * N  # 本のpと同じ 最短経路木における親を記録する

    # スタートとするノードについて初期化
    D[s] = 0  # スタートまでの距離は必ず0
    P[s] = None  # 親がない(ROOTである)ことを示す

    while True:
        # 最短経路候補の中で一番コストの少ないノードを選ぶ、あとその時のコストも
        min_cost = INF
        for i in range(N):
            if Color[i] != 2 and D[i] < min_cost:
                # 訪問済みでなく、最小コストを更新したら
                min_cost = D[i]
                u = i
        # uには次に確定するノードが入っている

        if min_cost == INF:
            # これ以上辺がない or すべて訪問済みなら
            break

        Color[u] = 2  # uは訪問済み これから最短経路木に突っ込む作業をする

        # 以下のforではsからの最短経路木にuを追加したときの更新、uまわりで次の最短経路になる候補の更新をしている
        for v in range(N):
            if Color[v] != 2 and adj_mat[u][v] != INF:
                # 訪問済みでなく、u→vへの経路が存在するならば
                if D[u] + adj_mat[u][v] < D[v]:  # ココがprimと異なる点である
                    # 今までのs→vへの距離の候補(D[v])よりも、
                    # 新しいuを用いた経路(D[u] + M[u][v]はs→u→vの距離を示す)のほうが小さければ更新する
                    D[v] = D[u] + adj_mat[u][v]  # u周りにおける最短経路の候補の更新
                    P[v] = u  # sからの最短経路木の更新
                    Color[v] = 1  # 訪問経験ありに更新(この処理に関しては意味はない)

    return D, P


D, P = dijkstra(M, 0)

for i in range(N):
    print(i, D[i])