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: #!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxint


def main():
    num = int(stdin.readline())

    L = []
    for _ in xrange(num):
        L.append([int(s) for s in stdin.readline().split()])

    weight = [maxint] * num
    index = 0
    rearch = {0}
    total_c = 0

    while maxint not in rearch:
        min_v = min_c = maxint
        Li = L[index]
        for i in xrange(Li[1]):
            v = Li[i*2+2]
            if v in rearch:
                continue
            c = Li[i*2+3]
            weight[v] = min(weight[v], c + total_c)
            if min_c > c:
                min_c = c
                min_v = v
        index = min_v
        rearch.add(min_v)
        total_c += min_c

    weight[0] = 0
    for i, d in enumerate(weight):
        print(i, d)


main()

Python: INFINITY = 10 ** 10
WHITE = 0
GRAY = 1
BLACK = 2


n = int(input())
M = [[INFINITY] * n for _ in range(n)]

for _ in range(n):
    u, k, *list_num = map(int, input().split())

    for i in range(0, k * 2, 2):
        M[u][list_num[i]] = list_num[i + 1]

d = [INFINITY] * n

def dijkstra():
    color = [WHITE] * n
    p = [None] * n

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

    while True:
        cost_min = INFINITY
        for i in range(n):
            if color[i] != BLACK and d[i] < cost_min:
                cost_min = d[i]
                top_now = i

        if cost_min == INFINITY:
            break
    
        color[top_now] = BLACK

        for v in range(n):
            if color[v] == BLACK or M[top_now][v] == INFINITY:
                continue

            cost_now = d[top_now] + M[top_now][v]
            if cost_now < d[v]:
                d[v] = cost_now
                p[v] = top_now
                color[v] = GRAY


dijkstra()

for i, cost in enumerate(d):
    print(i, cost)

Python: n = int(input())
C = [[] for _ in range(n)]
for _ in range(n):
    tmp = list(map(int,input().split()))
    for i in range(1,tmp[1]+1):
        C[tmp[0]].append(tuple(tmp[2*i:2*i+2]))


def dijkstra(start = 0):
    INF = 100000000
    d = [INF]*n
    visited = [False]*n

    d[start] = 0
    visited[start] = True
    S = {start}

    while 1:
        for s in S:
            for adj_weight in C[s]:
                if visited[adj_weight[0]] == False:
                    d[adj_weight[0]] = min(d[s] + adj_weight[1],d[adj_weight[0]])
        
        min_d = INF
        min_node = -1
        for i in range(n):
            if visited[i] == False and d[i] < min_d:
                min_d = d[i]
                min_node = i
        if min_node == -1:
            break
        else:
            visited[min_node] = True
            S.add(min_node)
    return d

ans = dijkstra()
for i in range(n):
    print("{} {}".format(i,ans[i]))

Python: def relax(u, v, w):
    if D[u] + w < D[v]:
        D[v] = D[u] + w
        P[v] = u

INF = float('inf')
N = int(input())
D = [INF for i in range(N)]
P = [None for i in range(N)]
C = ['w' for i in range(N)]
D[0] = 0

G = [[INF for j in range(N)] for i in range(N)]
for i in range(N):
    x = list(map(int, input().split()))
    g = x[2:]
    for j, n in enumerate(g):
        if j % 2 == 0:
            G[i][n] = g[j + 1]


while True:
    mincost = INF
    u = -1
    for i in range(N):
        if C[i] != 'b' and D[i] < mincost:
            mincost = D[i]
            u = i
    if u == -1:
        break
    C[u] = 'b'
    for v, w in enumerate(G[u]):
        if w != INF and C[v] != 'b':
            relax(u, v, w)
            C[v] = 'g'

for i, d in enumerate(D):
    print('{0} {1}'.format(i, d))

Python: from heapq import heappush, heappop
from collections import deque

def main():
    INF = float('inf')
    V = int(input())
    dist = [INF] * V
    visited = [False] * V
    graph = [None] + [deque() for i in range(V-1)]
    
    q = []
    tmp = list(map(int, input().split()))
    for i in range(tmp[1]): heappush(q, (tmp[2+2*i+1], tmp[2+2*i]))
        
    for i in range(1, V):
        tmp = list(map(int, input().split()))
        
        for j in range(tmp[1]):
            graph[i].append((tmp[2+2*j+1], tmp[2+2*j]))
        
    dist[0], visited[0] = 0, True
        
    while q:
        cost, v = heappop(q)
        if visited[v]: continue
    
        visited[v] = True
        dist[v] = cost
        
        for c, u in graph[v]:
            if visited[u] or dist[u] < cost + c: continue
            heappush(q, (cost+c, u))
    
    for i in range(V): print(i, dist[i])
        
if __name__ == '__main__':
    main()