Go: package main

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

const (
	MAX_N      = 100
	MAX_WEIGHT = 100000
)

type Edge struct {
	start  int
	end    int
	weight int
}

type ShortestInfo struct {
	edges    []Edge
	shortest int
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	n, err := nextInt(sc)
	if err != nil {
		panic(err)
	}

	shortestList := make([]ShortestInfo, n)
	for i := 1; i < n; i++ {
		shortestList[i] = ShortestInfo{edges: []Edge{}, shortest: MAX_N*MAX_WEIGHT + 1}
	}

	adjacentMatrix, err := createAdjacentMatrix(n, sc)
	if err != nil {
		panic(err)
	}

	sssp([]int{1}, shortestList, adjacentMatrix)
	for _, v := range shortestList {
		fmt.Printf("%d %d\n", v.getEnd()-1, v.shortest)
	}
}

func (si ShortestInfo) getEnd() int {
	if len(si.edges) == 0 {
		return 1
	} else {
		return si.edges[len(si.edges)-1].end
	}
}

func createAdjacentMatrix(n int, sc *bufio.Scanner) ([][]int, error) {
	adjacentMatrix := make([][]int, n)
	for i := 0; i < n; i++ {
		id, err := nextInt(sc)
		if err != nil {
			return nil, err
		}
		adjacentMatrix[id] = make([]int, n)
		for j := 0; j < n; j++ {
			adjacentMatrix[id][j] = -1
		}
		vertexNum, err := nextInt(sc)
		if err != nil {
			return nil, err
		}
		for j := 0; j < vertexNum; j++ {
			v, err := nextInt(sc)
			if err != nil {
				return nil, err
			}
			c, err := nextInt(sc)
			if err != nil {
				return nil, err
			}
			adjacentMatrix[id][v] = c
		}
	}
	return adjacentMatrix, nil
}

func sssp(nodeStack []int, shortestList []ShortestInfo, adjacentMatrix [][]int) {
	for len(nodeStack) > 0 {
		currentNode := nodeStack[0]
		nodeStack = nodeStack[1:]
		currentShortest := getShortest(currentNode, shortestList)
		adjacents := findAdjacents(currentNode, adjacentMatrix)
		for i := 0; i < len(adjacents); i++ {
			adj := adjacents[i]
			if currentShortest.shortest+adj.weight < getShortest(adj.end, shortestList).shortest {
				setShortest(adj.end, adj, currentShortest, shortestList)
				nodeStack = append(nodeStack, adj.end)
			}
		}
	}
}

func getShortest(node int, shortestList []ShortestInfo) ShortestInfo {
	return shortestList[node-1]
}

func setShortest(node int, edge Edge, currentShortest ShortestInfo, shortestList []ShortestInfo) {
	newEdges := make([]Edge, len(currentShortest.edges)+1)
	for i := 0; i < len(newEdges)-1; i++ {
		newEdges[i] = currentShortest.edges[i]
	}
	newEdges[len(newEdges)-1] = edge
	shortestInfo := ShortestInfo{edges: newEdges, shortest: currentShortest.shortest + edge.weight}
	shortestList[node-1] = shortestInfo
}

func findAdjacents(currentNode int, adjacentMatrix [][]int) []Edge {
	adjacents := adjacentMatrix[currentNode-1]
	edges := []Edge{}
	for i, v := range adjacents {
		if v > 0 {
			edges = append(edges, Edge{start: currentNode, end: i + 1, weight: v})
		}
	}
	return edges
}

func nextInt(sc *bufio.Scanner) (int, error) {
	sc.Scan()
	return strconv.Atoi(sc.Text())
}

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])