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: inf = float("inf")


class Node():

    def __init__(self, _id):
        self.id = _id
        self.d = inf
        self.pi = None
        self.color = 0
        self.adj = {}

    def input_data(self, data):
        k = data[0]
        for i in range(k):
            self.adj[G[data[2 * i + 1]]] = data[2 * i + 2]

    def __hash__(self):
        return hash(self.id)

def dijkstra():
    while True:
        mincost = inf
        for i in G:
            if i.color != 1 and i.d < mincost:
                mincost = i.d
                u = i
        if mincost == inf:
            break
        u.color = 1
        for v in u.adj.keys():
            if v.color != 1 and u.d + u.adj[v] < v.d:
                v.pi = u
                v.d = u.d + u.adj[v]

if __name__ == "__main__":
    n = int(input())
    G = [Node(i) for i in range(n)]
    for _ in range(n):
        data = [int(i) for i in input().split()]
        G[data[0]].input_data(data[1:])
        if data[0] == 0:
            G[data[0]].d = 0
    dijkstra()
    [print(i.id, i.d) for i in G]

Python: #!/usr/bin/env python3
import sys
import heapq
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7

n=int(input())
G=[[] for i in range(n)]
for _ in range(n):
    inp = list(map(int,input().split()))
    u,k=inp[:2]
    for i in range(k):
        G[u].append((inp[2+2*i],inp[3+2*i]))

def disktra(g,s):
    n=len(g)
    dist = [inf]*n
    dist[s] = 0
    hq=[]
    heapq.heappush(hq,(dist[s],s))
    while hq:
        cost,u =heapq.heappop(hq)
        if dist[u] < cost:
            continue
        for v,c in g[u]:
            if dist[v] <= dist[u] +c:
                continue
            dist[v] = dist[u] + c
            heapq.heappush(hq,(dist[v],v))
    return dist

d=disktra(G,0)
for i in range(n):
    print(i,d[i])

Python: # Single Source Shortest Path 1
INF = 10**10
N = int(input())
W = [[INF]*(N) for _ in [0]*(N)]

for _ in [0]*N:
    v, k, *A = map(int, input().split())
    for u, c in zip(*[iter(A)]*2):
        W[v][u] = c

S = set()
d = [INF]*N

d[0] = 0
while len(S) < N:
    dmin = INF
    v = -1
    for i in range(N):
        if i not in S and d[i] < dmin:
            dmin = d[i]
            v = i

    S.add(v)
    for u, w in enumerate(W[v]):
        if d[v]+w < d[u]:
            d[u] = d[v]+w

for i in range(N):
    print(i, d[i])

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()