Go: package main

import (
	"bufio"
	"bytes"
	"fmt"
	"io"
	"os"
	"strconv"
	"strings"
)

const (
	INFTY = 1 << 21
	NIL   = -1
)

const (
	WHITE = iota
	GRAY
	BLACK
)

type Graph [][]int

func (g *Graph) dikstra(n int) string {
	var (
		u, minv = 0, 0
	)

	d := make([]int, n)
	color := make([]int, n)

	for i := 0; i < n; i++ {
		d[i] = INFTY
		color[i] = WHITE
	}
	d[0] = 0
	color[0] = GRAY

	for {
		minv = INFTY
		u = -1
		for i := 0; i < n; i++ {
			if minv > d[i] && color[i] != BLACK {
				u = i
				minv = d[i]
			}
		}

		if u == -1 {
			break
		}

		color[u] = BLACK
		for v := 0; v < n; v++ {
			if color[v] != BLACK && (*g)[u][v] != INFTY {
				if d[v] > d[u]+(*g)[u][v] {
					d[v] = d[u] + (*g)[u][v]
					color[v] = GRAY
				}
			}
		}
	}

	var out bytes.Buffer
	for i := 0; i < n; i++ {
		out.WriteString(fmt.Sprintf("%d ", i))
		if d[i] == INFTY {
			out.WriteString(fmt.Sprintf("%d\n", -1))
			continue
		}
		out.WriteString(fmt.Sprintf("%d\n", d[i]))
	}

	return strings.TrimRight(out.String(), "\n")
}

func answer(reader io.Reader) string {
	sc := bufio.NewScanner(reader)
	sc.Split(bufio.ScanWords)

	sc.Scan()
	n, _ := strconv.Atoi(sc.Text())

	g := make(Graph, n)
	for i := 0; i < n; i++ {
		g[i] = make([]int, n)
		for j := 0; j < n; j++ {
			g[i][j] = INFTY
		}
	}

	for i := 0; i < n; i++ {
		sc.Scan()
		u, _ := strconv.Atoi(sc.Text())
		sc.Scan()
		k, _ := strconv.Atoi(sc.Text())

		for j := 0; j < k; j++ {
			sc.Scan()
			v, _ := strconv.Atoi(sc.Text())
			sc.Scan()
			c, _ := strconv.Atoi(sc.Text())

			g[u][v] = c
		}
	}

	return g.dikstra(n)
}

func main() {
	fmt.Println(answer(os.Stdin))
}

Python: # -*- coding: utf-8 -*-
from heapq import heappop, heappush


def dijkstra(edges, start, *, adj_matrix=False, default_value=float('inf')):
    '''
    Returns best costs to each node from 'start' node in the given graph.
    (Single Source Shortest Path - SSSP)

    If edges only include costs and destination nodes on possible edges,
    adj_matrix should be False(default), and it is generally when this functions works much faster

    Note that costs in edges should follow the rules below
    1. The cost from a node itself should be 0,
    2. If there is no edge between nodes, the cost between them should be default_value
    3. The costs can't be negative

    # sample input when given as adjacency matrix (adj_matrix=True)
    edges = [[0, 2, 5, 4, inf, inf],           # node 0
             [2, 0, inf, 3, 6, inf],           # node 1
             [5, inf, 0, 2, inf, 6],           # node 2
             [4, 3, 2, 0, 2, inf],             # node 3
             [inf, 6, inf, 2, 0, 4],           # node 4
             [inf, inf, 6, inf, 4, 0]]         # node 5

    # sample input when given not as adjacency matrix (adj_matrix=False)
    edges = [[(1, 2), (2, 5), (3, 4)],         # node 0
             [(0, 2), (3, 3), (4, 6)],         # node 1
             [(0, 5), (3, 2), (5, 6)],         # node 2
             [(0, 4), (1, 3), (2, 2), (4, 2)], # node 3
             [(1, 6), (3, 2), (5, 4)],         # node 4
             [(2, 6), (4, 4)]]                 # node 5
    '''

    n = len(edges)

    inf = float('inf')
    costs = [inf] * n
    costs[start] = 0
    pq, rem = [(0, start)], n - 1

    while pq and rem:
        tmp_cost, tmp_node = heappop(pq)
        if costs[tmp_node] < tmp_cost:
            continue
        rem -= 1

        nxt_edges = ((node, cost) for node, cost in enumerate(edges[tmp_node]) if cost != default_value) if adj_matrix else\
                    edges[tmp_node]

        for nxt_node, nxt_cost in nxt_edges:
            new_cost = tmp_cost + nxt_cost
            if costs[nxt_node] > new_cost:
                costs[nxt_node] = new_cost
                heappush(pq, (new_cost, nxt_node))

    return costs


def dijkstra_route(edges,
                   start,
                   goal,
                   *,
                   adj_matrix=False,
                   default_value=float('inf'),
                   verbose=False):
    '''
    Trys to find the best route to the 'goal' from the 'start'
    '''

    n = len(edges)

    inf = float('inf')
    costs = [inf] * n
    costs[start] = 0
    pq, rem = [(0, start)], n - 1
    prevs = [-1 for _ in [None] * n]

    while pq and rem:
        tmp_cost, tmp_node = heappop(pq)
        if costs[tmp_node] < tmp_cost:
            continue
        rem -= 1

        nxt_edges = ((node, cost) for node, cost in enumerate(edges[tmp_node]) if cost != default_value) if adj_matrix else\
                    edges[tmp_node]

        for nxt_node, nxt_cost in nxt_edges:
            new_cost = tmp_cost + nxt_cost
            if costs[nxt_node] > new_cost:
                costs[nxt_node] = new_cost
                heappush(pq, (new_cost, nxt_node))
                prevs[nxt_node] = tmp_node

    min_route = []
    prev = goal
    cnt = 0
    while prev != start:
        min_route.append(prev)
        prev = prevs[prev]

        cnt += 1
        if prev == -1 or cnt > n:
            raise NoRouteError(
                'There is no possible route in this graph \nedges: {} \nstart: {} \ngoal: {}'.
                format(edges, start, goal))

    else:
        min_route.append(prev)
    min_route = min_route[::-1]
    min_cost = costs[goal]

    if verbose:
        print('---route---')
        for node in min_route[:-1]:
            print('{} -> '.format(node), end='')
        else:
            print(min_route[-1])

        print('---distance---')
        print(min_cost)

    return costs, min_route


class NoRouteError(Exception):
    pass


if __name__ == '__main__':
    '''
    an example of using this function
    AIZU ONLINE JUDGE - ALDS_1_12_B
    '''

    n = int(input())
    edges = [[] for i in range(n)]
    for i in range(n):
        i, k, *kedges = map(int, input().split())
        for edge in zip(kedges[::2], kedges[1::2]):
            edges[i].append(edge)

    for i, cost in enumerate(dijkstra(edges, 0)):
        print(i, cost)

Python: INF = 1e9

n = int(input())
adj_matrix = [[INF for i in range(n)] for j in range(n)]

for i in range(n):
    u, k, *line = list(map(int, input().split()))
    for j in range(k):
        adj_matrix[u][line[2*j]] = line[2*j+1]

def dijkstra(x):
    isVisited = [False] * x
    d = [INF] * x 
    d[0] = 0
    p = [0] * x 
    
    while True:
        min_cost = INF
        
        for i in range(x):
            if isVisited[i] != True and d[i] < min_cost:
                min_cost = d[i]
                u = i
        
        if min_cost == INF:
            break
        
        isVisited[u] = True
        
        for v in range(x):
            if isVisited[v] != True and adj_matrix[u][v] != INF:
                if d[u] + adj_matrix[u][v] < d[v]:
                    d[v] = d[u] + adj_matrix[u][v]
                    p[v] = u
    return d

for i, di in enumerate(dijkstra(n)):
    print(i, di)

Python: def dijkstra(matrix, s):
    INF = 200000
    n = len(matrix)
    state, d, p = [False] * n, [INF] * n, [-1] * n
    d[s] = 0
    while True:
        mincost = INF
        for i in range(n):
            if not state[i] and d[i] < mincost:
                mincost = d[i]
                u = i
        if mincost == INF:
            break
        state[u] = True
        for v in range(n):
            if not state[v] and matrix[u][v] != -1:
                if d[u] + matrix[u][v] < d[v]:
                    d[v] = d[u] + matrix[u][v]
                    p[v] = u
    return d


def main():
    n = int(input())
    m = [[-1] * n for _ in range(n)]
    for _ in range(n):
        u, k, *vc = map(int, input().split())
        for v, c in zip(vc[::2], vc[1::2]):
            m[u][v] = c
    dist = dijkstra(m, 0)
    for i, d in enumerate(dist):
        print(i, d)


if __name__ == '__main__':
    main()