Go: package main

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

type Node struct {
	Id int
	Dis int
}

type PriorityQueue []*Node

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].Dis < pq[j].Dis
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x interface{}) {
	*pq = append(*pq, x.(*Node))
}

func (pq *PriorityQueue) Pop() interface{} {
	n := len(*pq)
	pop := (*pq)[n-1]
	*pq = (*pq)[0:n-1]
	return pop
}

func main() {
	var n int
	fmt.Scan(&n)

	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	g := make([][]int, n)
	c := make([][]int, n)
	pq := make(PriorityQueue, 0, n)
	d := make([]int, n)
	for i := 0; i < n; i++ {
		sc.Scan()
		u, _ := strconv.Atoi(sc.Text())
		sc.Scan()
		k, _ := strconv.Atoi(sc.Text())
		g[u] = make([]int, k)
		c[u] = make([]int, k)
		for j := 0; j < k; j++ {
			sc.Scan()
			g[u][j], _ = strconv.Atoi(sc.Text())
			sc.Scan()
			c[u][j], _ = strconv.Atoi(sc.Text())
		}

		if u == 0 {
			d[u] = 0
		} else {
			d[u] = 1 << 30
		}
		pq.Push(&Node{u, d[u]})
	}
	heap.Init(&pq)

	for pq.Len() > 0 {
		node := heap.Pop(&pq).(*Node)
		for i := 0; i < len(g[node.Id]); i++ {
			nextId := g[node.Id][i]
			nextDis := node.Dis + c[node.Id][i]
			if nextDis < d[nextId] {
				d[nextId] = nextDis
				heap.Push(&pq, &Node{nextId, nextDis})
			}
		}
	}

	wr := bufio.NewWriter(os.Stdout)
	for i := 0; i < n; i++ {
		wr.WriteString(strconv.Itoa(i))
		wr.WriteString(" ")
		wr.WriteString(strconv.Itoa(d[i]))
		wr.WriteString("\n")
	}
	wr.Flush()
}

Python: # -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_12_C

???????§????????????????II
"""
from enum import Enum
from heapq import heappush, heappop, heapify
import itertools


class Priority_queue():
    # https://docs.python.jp/3/library/heapq.html
    def __init__(self):
        self.pq = []                         # list of entries arranged in a heap
        self.entry_finder = {}               # mapping of tasks to entries
        self.REMOVED = '<removed-task>'      # placeholder for a removed task
        self.counter = itertools.count()     # unique sequence count

    def add_task(self, task, priority=0):
        'Add a new task or update the priority of an existing task'
        if task in self.entry_finder:
            self.remove_task(task)
        count = next(self.counter)
        entry = [priority, count, task]
        self.entry_finder[task] = entry
        heappush(self.pq, entry)

    def remove_task(self, task):
        'Mark an existing task as REMOVED.  Raise KeyError if not found.'
        entry = self.entry_finder.pop(task)
        entry[-1] = self.REMOVED

    def pop_task(self):
        'Remove and return the lowest priority task. Raise KeyError if empty.'
        while self.pq:
            priority, count, task = heappop(self.pq)
            if task is not self.REMOVED:
                del self.entry_finder[task]
                return task
        raise KeyError('pop from an empty priority queue')

    def top_task(self):
        return self.pq[0][-1]

    def get_length(self):
        return len(self.pq)

    def is_empty(self):
        return self.get_length()==0


class Sssp(object):
    """ single source shortest path """
    INFINITY = 999999999
    class Status(Enum):
        """ ?????????????¨??????¶??? """
        white = 1  # ????¨????
        gray = 2  # ?¨???????
        black = 3  #?¨???????

    def __init__(self, data):
        num_of_nodes = len(data)
        self.color = [Sssp.Status.white] * num_of_nodes  # ????????????????¨??????¶???
        self.d = [Sssp.INFINITY] * num_of_nodes  # ?§???????????????????
        self.p = [-1] * num_of_nodes  # ????????????????????????????¨?????????????????????????
        self.adj = [[] for _ in range(num_of_nodes)]
        self.make_adj(data)


    def make_adj(self, data):
        # ??£??\??????????????????
        for d in data:
            my_id = d[0]
            d = d[2:]
            while len(d) > 1:
                to_node, cost = d[0], d[1]
                self.adj[my_id].insert(0, (to_node, cost))
                d = d[2:]


    def dijkstra(self, start):
        self.d[start] = 0
        pq = Priority_queue()
        pq.add_task((0, 0), 0)

        while not pq.is_empty():
            cost, u = pq.pop_task()
            self.color[u] = Sssp.Status.black
            if self.d[u] < cost:
                continue

            for n, cost in self.adj[u]:
                if n is None:
                    break
                v = n
                if self.color[v] == Sssp.Status.black:
                    continue
                if self.d[v] > self.d[u] + cost:
                    self.d[v] = self.d[u] + cost
                    pq.add_task((self.d[v], v), cost)
                    self.color[v] = Sssp.Status.gray


if __name__ == '__main__':
    # ??????????????\???
    num = int(input())
    data = []
    for i in range(num):
        data.append(list(map(int, input().split(' '))))

    # ???????????¢?´¢
    s = Sssp(data)
    s.dijkstra(0)

    # ???????????¨???
    for i in range(num):
        print('{0} {1}'.format(i, s.d[i]))

Python: import sys
from heapq import*
def m():
 n=int(input())
 A=[]
 for e in sys.stdin:
  e=list(map(int,e.split()))
  A+=[zip(e[2::2],e[3::2])]
 d=[0]+[float('inf')]*n
 H=[(0,0)]
 while H:
  u=heappop(H)[1]
  for v,c in A[u]:
   t=d[u]+c
   if d[v]>t:
    d[v]=t
    heappush(H,(t,v))
 print('\n'.join(f'{i} {d[i]}'for i in range(n)))
m()

Python: #!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	single_source_shortest_path
# CreatedDate:  2020-06-08 21:54:58 +0900
# LastModified: 2020-06-08 22:28:47 +0900
#


import os
import sys
from collections import deque
#import numpy as np
#import pandas as pd


def main():
    n = int(input())
    graph = [[] for _ in range(n)]
    for _ in range(n):
        line = list(map(int,input().split()))
        u,k = line[0],line[1]
        path = line[2:]
        for i in range(0,2*k,2):
            graph[u].append([path[i+1],path[i]])
    
#    print(graph)
    s=0
    distance=[-1]*n
    Q = deque([s])
    distance[0]=0
    

    while Q:
        u = Q.popleft()
        for dis,v in graph[u]:
            if distance[v]==-1:
                distance[v]=distance[u]+dis
                Q.append(v)

            if distance[v]>distance[u]+dis:
                distance[v]=distance[u]+dis
                Q.append(v)
            


    for i,dis in enumerate(distance):
        print(i,dis)


if __name__ == "__main__":
    main()

Python: from heapq import*
def m():
 n=int(input())
 A=[[]for _ in[0]*n]
 for _ in[0]*n:
  e=list(map(int,input().split()))
  for i in range(e[1]):k=2*-~i;A[e[0]]+=[(e[k],e[k+1])]
 H=[[0,0]]
 d=[0]+[1e6]*n
 c=[1]*n
 while H:
  f=heappop(H)
  u=f[1]
  c[u]=0
  if d[u]>=f[0]:
   for s in A[u]:
    v=s[0]
    if c[v]and d[v]>d[u]+s[1]:
     d[v]=d[u]+s[1]
     heappush(H,[d[v],v])
 for i in range(n):print(i,d[i])
m()