Go: package main

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

const NIL = -1

type Node struct {
	id     int
	weight int
}

func init() {
	sc.Split(bufio.ScanWords)
}

type NodeHeap []Node

func (h NodeHeap) Len() int           { return len(h) }
func (h NodeHeap) Less(i, j int) bool { return h[i].weight < h[j].weight }
func (h NodeHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *NodeHeap) Push(x interface{}) {
	*h = append(*h, x.(Node))
}

func (h *NodeHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	num, _ := strconv.Atoi(scanString())
	return num
}

func scanString() string {
	sc.Scan()
	return sc.Text()
}

func init() {
	sc.Split(bufio.ScanWords)
}

func main() {
	n := scanInt()

	route := make([][]Node, n)
	weight := make([]int, n)
	for i := 0; i < n; i++ {
		weight[i] = NIL
	}

	for i := 0; i < n; i++ {
		u := scanInt()
		k := scanInt()
		route[i] = make([]Node, k)
		for j := 0; j < k; j++ {
			route[u][j] = Node{id: scanInt(), weight: scanInt()}
		}
	}

	start := Node{id: 0, weight: 0}
	h := &NodeHeap{start}
	heap.Init(h)

	for h.Len() > 0 {
		node := heap.Pop(h).(Node)
		if weight[node.id] != NIL {
			continue
		}
		weight[node.id] = node.weight

		for _, nextNode := range route[node.id] {
			if weight[nextNode.id] != NIL {
				continue
			}
			nextNode.weight += node.weight
			heap.Push(h, nextNode)
		}
	}

	for i, w := range weight {
		fmt.Println(i, w)
	}
}

Python: import heapq

n = int(input())
G = [[] for i in range(n)]
for ni in range(n):
    u, k, *tmp = [int(i) for i in input().split()]
    for ki in range(k):
        G[ni].append(tmp[:2])
        del tmp[:2]

INF = 100*100000
D = [INF for i in range(n)]
D[0] = 0
C = [0 for i in range(n)]
U = []
u = 0
while 0 in C:
    i = 0
    while U != []:
        u = heapq.heappop(U)[1]
        if C[u] == 0:
            break

    for i in range(len(G[u])):
        v = G[u][i][0]
        if D[u] + G[u][i][1] < D[v]:
            D[v] = D[u] + G[u][i][1]
            heapq.heappush(U, [D[v], v])
    C[u] = 1

for ni in range(n):
    print(ni, D[ni])

Python: import sys

f_i = sys.stdin

n = int(f_i.readline())

adj = [[]] * n
for x in f_i:
    x = list(map(int, x.split()))
    adj[x[0]] = [c_v for c_v in zip(x[3::2], x[2::2])]

import heapq

def dijkstra():
    PQ = [(0, 0)]
    isVisited = [False] * n
    distance = [999900001] * n

    distance[0] = 0
    
    while PQ:
        uc, u = heapq.heappop(PQ)

        if uc > distance[u]:
            continue

        isVisited[u] = True
        
        for vc, v in adj[u]:
            if isVisited[v] == False:
                t_cost = distance[u] + vc
                if t_cost < distance[v]:
                    distance[v] = t_cost
                    heapq.heappush(PQ, (t_cost, v))

    for v, d in enumerate(distance):
        print(v, d)


dijkstra()

Python: n = int(input())
G = [[[], []] for j in range(n)]
d = [999999 for i in range(n)]
  
for i in range(n):
    v = input().split()
    for j in range(int(v[1])):
        G[int(v[0])][0].append(int(v[2+2*j]))
        G[int(v[0])][1].append(int(v[3+2*j]))

d = [999999] * n
flag = [0] * n
d[0] = 0
while True:
    v = -1
    for j in range(n):
        if flag[j] != 1 and (v == -1 or d[j] < d[v]):
            v = j
    if v == -1:
        break
    flag[v] = 1
    for j in range(n):
        if j not in G[v][0]: continue
        i = 0
        while True:
            if G[v][0][i] == j:
                d[j] = min(d[j], d[v] + G[v][1][i])
                break
            i += 1

for i in range(n):
    print(str(i) + " " + str(d[i]))

Python: inf = float('inf')
n = int(input())
g = []
for i in range(n):
    line = list(map(int, input().split()[2:]))
    g.append(zip(line[0::2], line[1::2]))

distance = [inf] * n
distance[0] = 0
visited = [False] * n
current = 0

while not all(visited):
    visited[current] = True
    for v, c in g[current]:
        if not visited[v] and distance[current] + c < distance[v]:
            distance[v] = distance[current] + c
    min_i = 0
    min_d = inf
    for i in range(n):
        if not visited[i] and distance[i] < min_d:
            min_i = i
            min_d = distance[i]
    current = min_i

for i in range(n):
    print(i, distance[i])

Python: N = int(input())
G = [[] for i in range(N)]
for nod in range(N):
    tmp = list(map(int, input().split()))
    for i in range(2, tmp[1]*2+1, 2):
        edge, cos = tmp[i], tmp[i+1]
        G[nod].append([edge, cos])



import heapq


def dijkstra(x):
    d = [float('inf')] * N
    d[x] = 0
    visited = {x}

    # d, u
    hq = [(0, x)]

    while hq:
        u = heapq.heappop(hq)[1]
        visited.add(u)

        for node, cost in G[u]:
            if (node not in visited) and d[node] > d[u] + cost:
                d[node] = d[u] + cost
                heapq.heappush(hq, (d[u]+cost, node))
    return d


distance = dijkstra(0)
#print(distance)
for i in range(N):
    print(i, distance[i])

N = int(input())
G = [[] for i in range(N)]
for nod in range(N):
    tmp = list(map(int, input().split()))
    for i in range(2, tmp[1]*2+1, 2):
        edge, cos = tmp[i], tmp[i+1]
        G[nod].append([edge, cos])



import heapq


def dijkstra(x):
    d = [float('inf')] * N
    d[x] = 0
    visited = {x}

    # d, u
    hq = [(0, x)]

    while hq:
        u = heapq.heappop(hq)[1]
        visited.add(u)

        for node, cost in G[u]:
            if (node not in visited) and d[node] > d[u] + cost:
                d[node] = d[u] + cost
                heapq.heappush(hq, (d[u]+cost, node))
    return d


distance = dijkstra(0)
#print(distance)
for i in range(N):
    print(i, distance[i])

Python: import sys

f_i = sys.stdin

n = int(f_i.readline())

adj = [[(int(cost), int(v_n)) for v_n, cost in zip(x.split()[2::2], x.split()[3::2])] for x in f_i]

import heapq

def dijkstra():
    PQ = [(0, 0)]
    isVisited = [False] * n
    distance = [999900001] * n

    distance[0] = 0
    
    while PQ:
        uc = heapq.heappop(PQ)
        u = uc[1]

        if uc[0] > distance[u]:
            continue

        isVisited[u] = True
        
        for vc in adj[u]:
            v = vc[1]
            if isVisited[v] == True:
                continue
            t_cost = distance[u] + vc[0]
            if t_cost < distance[v]:
                distance[v] = t_cost
                heapq.heappush(PQ, (t_cost, v))

    for v, d in enumerate(distance):
        print(v, d)


dijkstra()

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

WHITE = 0
GRAY = 1
BLACK = 2

INF = 2000000000


def dijkstra():
    PQ = []
    heapq.heapify(PQ)
    color = [WHITE] * n
    d = [INF] * n
    
    d[0] = 0
    heapq.heappush(PQ, (0, 0))
    color[0] = GRAY
    
    while len(PQ) != 0:
        
        f = heapq.heappop(PQ)
        u = f[1]
        color[u] = BLACK
        
        if d[u] < f[0]:
            continue
        
        for j in range(len(adj[u])):
            v = adj[u][j][0]
            if color[v] == BLACK:
                continue
            if d[v] > d[u] + adj[u][j][1]:
                d[v] = d[u] + adj[u][j][1]
                heapq.heappush(PQ, (d[v], v))
                color[v] = GRAY
    for i in range(n):
        print(i, d[i])


n = int(input())

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

dijkstra()