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

C++: #include <stdio.h>
#include <iostream>
#include <queue>
using namespace std;

#define NIL -1
#define INF 100000000
#define WHITE 1
#define GREY 2
#define BLACK 3
#define N_MAX 10000

int G[N_MAX][N_MAX];
int V[N_MAX];
int V_value[N_MAX];

void init(){
    for(int i = 0; i < N_MAX; i++){
        V[i] = WHITE;
        V_value[i] = INF;
    }

    for(int i = 0; i < N_MAX; i++){
        for(int j = 0; j < N_MAX; j++){
            G[i][j] = NIL;
        }
    }
}

int main(void){
    init();
    int n;
    scanf("%d\n", &n);

    for(int i = 0; i < n; i++){
        int u, k;
        scanf("%d %d", &u, &k);
        for(int j = 0; j < k; j++){
            int v, c;
            scanf("%d %d", &v, &c);
            G[u][v] = c;
        }
    }

    priority_queue<pair<int, int>> PQ;

    V[0] = BLACK;
    V_value[0] = 0;
    int new_node = 0;
    
    while(1){
        //printf("new_node: %d\n", new_node);
        for(int i = 0; i < n; i++){
            if(G[new_node][i] != NIL && V[i] == WHITE){
                V_value[i] = min(V_value[i], V_value[new_node] + G[new_node][i]);
                //printf("push %d %d\n",i,  V_value[i]);
                PQ.push(make_pair(V_value[i] * (-1), i));
            }
        }

        int min_value;
        int min_index = NIL;
        while(!PQ.empty()){
            pair<int, int> p = PQ.top(); PQ.pop();
            //printf("pop %d %d\n", p.second, p.first * (-1));
            if(p.first * (-1) == V_value[p.second] && V[p.second] == WHITE){
                min_value = p.first * (-1);
                min_index = p.second;
                break;
            }
        }

        if(min_index == NIL)
            break;

        new_node = min_index;
        V[new_node] = BLACK;
        V_value[new_node] = min_value;
    }
    
    for(int i = 0; i < n; i++){
        printf("%d %d\n", i, V_value[i]);
    }

    return 0;
}

C++: //By Vlgd
#include<bits/stdc++.h>
using namespace std;
const int N=10000;
const int INF=(1<<21);
struct edge{int w,v;};
struct path{int l,v;};
vector<edge>G[N];
int n,vis[N]={0},dis[N];
//priority_queue<path>pq;
path H[10*N];int h=0;
bool isempty(){return h==0;}
void insert(path p){
	int i=++h;
	H[i]=p;
	while(i>1&&H[i].l<H[i/2].l){
		swap(H[i],H[i/2]);
		i/=2;
	}
}
void heapify(int i){
	int les;
	if(i*2<=h&&H[i].l>H[2*i].l) les=2*i;
	else les=i;
	if(i*2+1<=h&&H[les].l>H[i*2+1].l) les=2*i+1;
	if(les!=i){
		swap(H[i],H[les]);
		heapify(les);
	}
}
path extract(){
	path p=H[1];
	H[1]=H[h--];
	if(h>1) heapify(1);
	return p;
} 
//
void dij(int s){
	for(int i=0;i<n;i++) dis[i]=INF;
	path p;
	dis[s]=0;
	p.l=0;p.v=0;
	insert(p);
	while(!isempty()){
		p=extract();
		int u=p.v;
		vis[u]=1;
		for(int i=0;i<G[u].size();i++){
			int v=G[u][i].v;
			int w=G[u][i].w;
			if(!vis[v]){
				if (dis[v]>dis[u]+w){
					p.l=dis[v]=dis[u]+w;
					p.v=v;
					insert(p);
				}
			}
		}
	}
}
int main(){
	scanf("%d",&n);
	int u,deg;edge e;
	for (int i=0;i<n;i++){
		scanf("%d%d",&u,&deg);
		for(int j=0;j<deg;j++){
			scanf("%d%d",&e.v,&e.w);
			G[u].push_back(e);
		}
	}
	dij(0);
	for (int i=0;i<n;i++) printf("%d %d\n",i,dis[i]);
	return 0;
}

C++: #include<stdio.h>
#define min(a,b) ((a)>(b))?(b):(a)
int main(void){
	int i,j,n,u,k,s,tmp,w,adj[100][100]={0};
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d %d",&u,&k);
		for(j=0;j<k;j++){
			scanf("%d %d",&tmp,&w);
			adj[u][tmp]=w;
		}
	}
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			if((adj[i][j]==0) && (i!=j)){
				adj[i][j]=100000000;
			}
		}
	}
	for(s=0;s<n;s++){
		for(i=0;i<n;i++){
			for(j=0;j<n;j++){
				adj[i][j]=min(adj[i][j],adj[i][s]+adj[s][j]);
			}
		}
	}
	for(i=0;i<n;i++){
		printf("%d %d\n",i,adj[0][i]);
	}
	return 0;
}

C++: #include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

const int INF = 0xfffffff;
const int MAX = 10000;

struct Edge {
	Edge() {};
	Edge(int v, int c) :v(v), c(c) {};
	bool operator < (const Edge& e)const {
		return c > e.c;
	}
	int v;
	int c;
};

int main() {
	int n;
	priority_queue<Edge> graph[MAX];
	vector<Edge> table;
	bool check[MAX] = { false };
	int ary[MAX] = { 0 };

	cin >> n;

	for (int i = 0; i < n; i++) {
		int u, k;
		cin >> u >> k;
		for (int j = 0; j < k; j++) {
			Edge e;
			cin >> e.v >> e.c;
			graph[u].push(e);
		}
	}

	Edge e(0, 0);
	table.push_back(e);
	check[0] = true;

	for (int i = 1; i < n; i++) {
		Edge minv(0, INF);
		int erase = 0;

		for (int j = 0; j < table.size(); j++) {
			int v = table[j].v;
			int c = table[j].c;	
			while (!graph[v].empty() && check[graph[v].top().v])graph[v].pop();
			if (graph[v].empty())continue;
			if (c + graph[v].top().c < minv.c) {
				minv.c = c + graph[v].top().c;
				minv.v = graph[v].top().v;
				erase = v;
			}
		}
		table.push_back(minv);
		check[minv.v] = true;
		graph[erase].pop();
	}
	
	for (int i = 0; i < n; i++) {
		ary[table[i].v] = table[i].c;
	}
	for (int i = 0; i < n; i++) {
		cout << i << " " << ary[i] << endl;
	}

	return 0;
}