Go: package main

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

func main() {
	r := bufio.NewReader(os.Stdin)

	var n int
	fmt.Fscan(r, &n)
	cs := make([]map[int]int, n) // []v_i -> c_i
	for h := 0; h < n; h++ {
		var u, k int
		fmt.Fscan(r, &u, &k)
		m := make(map[int]int)
		for i := 0; i < k; i++ {
			var v, c int
			fmt.Fscan(r, &v, &c)
			m[v] = c
		}

		cs[u] = m
	}

	q := make(map[int]int)
	q[0] = 0
	visited := make(map[int]struct{})
	out := make([]int, n)

	for len(q) > 0 {
		u := top(q)
		for uu, c := range cs[u] {
			// Consider the connection between u and uu.
			if _, ok := visited[uu]; ok {
				continue
			}
			if d, ok := q[uu]; !ok || d > q[u]+c {
				q[uu] = q[u] + c
			}
		}

		out[u] = q[u]
		delete(q, u)
		visited[u] = struct{}{}
	}

	for u, d := range out {
		fmt.Println(u, d)
	}
}

func top(q map[int]int) int {
	minu := -1
	min := -1
	for u, d := range q {
		if min < 0 || d < min {
			minu = u
			min = d
		}
	}

	return minu
}

Python: import heapq
N=int(input())
ad_li=[[]for i in range(N)]
for i in range(N):
    nums=list(map(int,input().split()))
    f=nums[0]
    for j in range(nums[1]):
        t=nums[j*2+2]
        c=nums[j*2+3]
        ad_li[f].append([t,c])

memo=[1E18 for i in range(N)]
memo[0]=0
qu=[]
heapq.heappush(qu,(0,0))
while len(qu)!=0:
    atop=heapq.heappop(qu)
    for ne in ad_li[atop[1]]:
        next_cost=atop[0]+ne[1]
        if(memo[ne[0]]>next_cost):
            memo[ne[0]]=next_cost
            heapq.heappush(qu,(next_cost,ne[0]))
for i in range(N):
    print(i,memo[i])

Python: INF = float('inf')


def dijkstra(source):
    distance[source] = 0
    parent[source] = -1

    while True:
        mincost = INF
        for i in range(n):
            if color[i] != 'black' and distance[i] < mincost:
                mincost = distance[i]
                u = i

        if mincost == INF:
            break

        color[u] = 'black'

        for v in range(n):
            if color[v] != 'black' and adjMat[u][v] != INF:
                if distance[u] + adjMat[u][v] < distance[v]:
                    distance[v] = distance[u] + adjMat[u][v]
                    parent[v] = u
                    color[v] = 'gray'


n = int(input())
color = ['white'] * n
parent = [-1] * n
distance = [INF] * n

adjMat = [[INF] * n for _ in range(n)]
for i in range(n):
    inputList = list(map(int, input().split()))
    adjRow = inputList[0::2][1:]
    weightRow = inputList[1::2][1:]
    for v, weight in zip(adjRow, weightRow):
        adjMat[i][v] = weight

dijkstra(0)

for index, distance in enumerate(distance):
    print(('{} {}').format(index, distance))

Python: import sys
input = sys.stdin.readline

INF = 10**9
WHITE = -100
GRAY = -1000
BLACK = -10000

def main():
	m = int(input().strip())
	s = [[-1] * m for _ in range(m)]
	for i in range(m):
		l = list(map(int, input().strip().split()))
		for j in range(l[1]):
			s[i][l[2 + 2 * j]] = l[3 + 2 * j]
	color = [WHITE] * m
	d = [INF] * m
	p = [-1] * m

	d[0] = 0
	# for i in range(m):
	# 	print(s[i])
	color[0] = BLACK
	u = 0
	while True:
		for i in range(m):
			if color[i] != BLACK and s[u][i] != -1:
				if d[u] + s[u][i] < d[i]:
					d[i] = d[u] + s[u][i]
					p[i] = u
		mincost = INF
		for i in range(m):
			if color[i] != BLACK and d[i] < mincost:
				mincost = d[i]
				u = i
		if mincost == INF:
			break
		color[u] = BLACK
	for i in range(m):
		print("{} {}".format(i, d[i]))


if __name__ == '__main__':
	main()

Python: def diikstraMethd(G, s):
    # ?????????
    n = len(G)
    # White:0 Gyay:1 Black:2
    color = [0 for _ in range(n)]
    d = [INF for _ in range(n)]
    p = [None for _ in range(n)]

    d[s] = 0

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

        if mincost == INF: break

        color[u] = 2

        for v in range(n):
            if color[v] != 2 and M[u][v] != INF:
                if d[u] + M[u][v] < d[v]:
                    d[v] = d[u] + M[u][v]
                    p[v] = u
                    color[u] = 1

    return d

if __name__ == '__main__':
    n = int(input())
    M = [[INF for _ in range(n)] for i in range(n)]
    for _ in range(n):
        tmp = list(map(int, input().split()))
        u = tmp.pop(0)
        k = tmp.pop(0)
        for _ in range(k):
            v = tmp.pop(0)
            c = tmp.pop(0)
            M[u][v] = c
    d = diikstraMethd(M, 0)

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

Python: from __future__ import division, print_function
from sys import stdin, maxint
 
 
def main():
    num = int(stdin.readline())
 
    y = []
    for _ in xrange(num):
        it = iter(int(s) for s in stdin.readline().split()[1:])
        y.append([(next(it), next(it)) for _ in xrange(next(it))])
 
    weight = [maxint] * num
    weight[0] = 0
    t = set(xrange(1, num))
    index = 0
 
    while t:
        for v, cost in y[index]:
            if v not in t:
                continue
            weight[v] = min(weight[v], cost + weight[index])
 
        index = min(t, key=lambda i: weight[i])
        t.remove(index)
 
    for i, d in enumerate(weight):
        print(i, d)
 
 
main()

Python: # coding: utf-8
# Your code here!

WHITE = 0
GRAY = 1
BLACK = 2

INF = 2000000000

def dijkstra(s):
    while True:
        u = 0
        mincost = INF
        for i in range(n):
            if color[i] != BLACK and d[i] < mincost:
                mincost = d[i]
                u = i
                
        if mincost == INF:
            break
    
        color[u] = BLACK
        
        for v in range(n):
            if color[v] != BLACK and m[i][v] != -1:
                if d[u] + m[u][v] < d[v]:
                    d[v] = d[u] + m[u][v]
                    p[v] = u
                    color[v] = GRAY

n = int(input())

m = [[INF for i in range(n)] for j in range(n)]
for i in range(n):
    nums=list(map(int,input().split()))
    for j in range(nums[1]):
        m[i][nums[2*j+2]] = nums[2*j+3]

color = [WHITE] * n
d = [INF] * n 
d[0] = 0
p = [-1] * n

dijkstra(0)
for v in range(n):
    print(v, d[v])

Python: # -*- coding: utf-8 -*-
"""
Created on Sat Jul 14 19:11:44 2018

@author: maezawa
"""
infinity = 2*10**9

n = int(input())
adj = [[] for _ in range(n)]

for j in range(n):
    ain = list(map(int, input().split()))
    u = ain[0]
    k = ain[1]
    for i in range(2,2+2*k,2):
        adj[u].append([ain[i],ain[i+1]])
    #print(*adj[u])

color = [0]*n
d = [infinity for _ in range(n)]
p = [0]*n
p[0] = -1
d[0] = 0

def dyk(s):
    cnt = 1
    cur = s
    candidates = set() # remaining nodes
    while True:
        for i, w in adj[cur]:
            if color[i] == 2:
                continue
            if d[i] > d[cur] + w:
                d[i] = d[cur] + w
                color[i] = 1
            candidates.add(i)
        min_d = infinity
        for j in candidates:
            if min_d > d[j]:
                min_node = j
                min_d = d[j]
        candidates.remove(min_node)
        p[min_node] = cur
        color[cur] = 2
        cur = min_node
        cnt += 1
        #print(cur, d)
        #print(candidates)
        if cnt == n:
            break
    return

dyk(0)
for i in range(n):
    print(i, d[i])