Go: package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
	"strconv"
)

//make priority queue
type Item struct {
	id       int
	priority int // this state is priority and distans from start
	index    int
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

// we want the ascending-priority-queue.
// So we use less than here.
func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].priority < pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = j
	pq[j].index = i
}

func (pq *PriorityQueue) Push(x interface{}) {
	n := len(*pq)
	item := x.(*Item)
	item.index = n
	*pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	item.index = -1 //for safety
	*pq = old[0 : n-1]
	return item
}

func (pq *PriorityQueue) update(dist int, id int) {
	for _, i := range *pq {
		if i.id == id {
			if i.priority > dist {
				i.priority = dist
			}
		}
	}
}

// the main code
func nextInt(sc *bufio.Scanner) int {
	sc.Scan()
	n, _ := strconv.Atoi(sc.Text())
	return n
}

func dikstra(dist *[][]int, n int) *[]int {
	// preparate priority queue
	inf := 1 << 30
	pq := make(PriorityQueue, n)
	shortests := make([]int, n)
	for i := 0; i < n; i++ {
		pq[i] = &Item{
			id:       i,
			priority: inf,
			index:    i,
		}

		shortests[i] = inf
	}
	pq[0].priority = 0
	shortests[0] = 0
	heap.Init(&pq)

	for pq.Len() > 0 {
		item := heap.Pop(&pq).(*Item)
		shortests[item.id] = item.priority
		for id, d := range (*dist)[item.id] {
			if d != -1 {
				pq.update(item.priority+d, id)
			}
		}
		heap.Init(&pq)
	}
	return &shortests
}

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

	// init
	n := nextInt(sc)
	dist := make([][]int, n)
	for i := 0; i < n; i++ {
		dist[i] = make([]int, n)
		for j := 0; j < n; j++ {
			dist[i][j] = -1
		}
	}

	// std Input
	for i := 0; i < n; i++ {
		u := nextInt(sc)
		k := nextInt(sc)
		for j := 0; j < k; j++ {
			v, c := nextInt(sc), nextInt(sc)
			dist[u][v] = c
		}
	}

	shortests := dikstra(&dist, n)
	for i, d := range *shortests {
		fmt.Printf("%d %d\n", i, d)
	}
}

Python: import queue

INFTY=1<<21

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

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

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

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

        #最も近い探索していない頂点
        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=[[] 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]].append([l[2*j+2],l[2*j+3]])

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

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

Python: from sys import maxsize
from heapq import heappop, heappush


class Node:
    WHITE = 0
    GRAY = 1
    BLACK = 2

    def __init__(self):
        self.adjs = []
        self.color = Node.WHITE
        self.dist = maxsize

    def __lt__(self, other):
        return self.dist < other.dist

    def __repr__(self):
        return "Node({},{},{})".format(self.adjs, self.color, self.dist)


def read_adj():
    n = int(input())
    nodes = [Node() for _ in range(n)]

    for i in range(n):
        u, _, *rest = [int(x) for x in input().split()]
        for i in range(0, len(rest) - 1, 2):
            nodes[u].adjs.append((rest[i], rest[i+1]))

    return nodes


def shortest_path(nodes):
    h = []

    nodes[0].dist = 0
    nodes[0].color = Node.GRAY
    heappush(h, (0, 0))

    while len(h) > 0:
        min_node, min_dist = heappop(h)
        if nodes[min_node].dist < min_dist:
            continue

        nodes[min_node].color = Node.BLACK

        for adj, c in nodes[min_node].adjs:
            if nodes[min_node].color == Node.BLACK:
                continue
            if nodes[min_node].dist + c < nodes[adj].dist:
                nodes[adj].dist = nodes[min_node].dist + c
                nodes[adj].color = Node.GRAY
                heappush(h, (adj, nodes[adj].dist))


def print_dist(nodes):
    for u, n in enumerate(nodes):
        print(u, n.dist)


def main():
    nodes = read_adj()
    shortest_path(nodes)
    print_dist(nodes)


if __name__ == '__main__':
    main()

Python: from sys import stdin
from collections import deque
import heapq

def read_graph(n):
    A = [ [] for _ in range(n) ]
    for _ in range(n):
        line = deque(stdin.readline().strip().split())
        u = line.popleft()
        line.popleft()
        for l, k in enumerate(line):
            if l % 2 == 0:
                v = k
            else:
                A[int(u)].append((int(v), int(k)))
    return A

def dijkstra(n, A, s):
    color = [ 'WHITE' for i in range(n) ]
    d = [ float('inf') for i in range(n) ]
    d[s] = 0
    pq = []

    heapq.heappush(pq, (s, 0))

    while pq:
        costu, u = heapq.heappop(pq)
        color[u] = 'BLACK'

        if d[u] < costu:
            continue

        for v, costv in A[u]:
            if color[v] != 'BLACK':
                if d[u] + costv < d[v]:
                    d[v] = d[u] + costv
                    color[v] = 'GRAY'
                    heapq.heappush(pq, (d[v], v))
    return d

n = int(input())
A = read_graph(n)
for i, k in enumerate(dijkstra(n, A, 0)):
    print(i, k)

Python: from heapq import heappop, heappush
import sys


class SSSP:
    """Given weighted graph, find Single Sorce Shortest Path from node 0.

    >>> st = SSSP([[(2, 3), (3, 1), (1, 2)], \
                   [(0, 2), (3, 4)], \
                   [(0, 3), (3, 1), (4, 1)], \
                   [(2, 1), (0, 1), (1, 4), (4, 3)], \
                   [(2, 1), (3, 3)]])
    >>> [st.weight(n) for n in range(5)]
    [0, 2, 2, 1, 3]
    """
    def __init__(self, graph):
        self.size = len(graph)
        self.tree = []
        self.weights = [0] * self.size
        self._search(graph)

    def weight(self, n):
        return self.weights[n]

    def _search(self, graph):
        h = []
        count = 1
        for i, w in graph[0]:
            heappush(h, (w, 0, i))

        while count < self.size:
            while len(h) > 0:
                weight, src, dst = heappop(h)
                if self.weights[dst] == 0 and dst > 0:
                    self.weights[dst] = weight
                    count += 1
                    self.tree.append((src, dst))
                    for i, w in graph[dst]:
                        if self.weights[i] == 0 and dst > 0:
                            heappush(h, (w+weight, dst, i))
                    break


def run():
    n = int(input())

    nodes = [None] * n
    for line in sys.stdin:
        id_, deg, *edges = [int(i) for i in line.split()]
        nodes[id_] = []
        for _ in range(deg):
            tgt, wgt, *edges = edges
            nodes[id_].append((tgt, wgt))

    st = SSSP(nodes)
    for node in range(n):
        print('{} {}'.format(node, st.weight(node)))


if __name__ == '__main__':
    run()