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<bits/stdc++.h>
#define ll long long
#define rep(i, n) for(int i=0; i<n; i++)
#define REP(i, n) for(int i=0; i<=n; i++)
#define repr(i, n) for(int i=n; i>0; i--)
#define REPR(i, n) for(int i=n; i>=0; i--)
const ll INF = 1LL<<60;
const int INT_INF = 1e9;
const ll MOD = 1e9+7;
template<class T> void puts(T x) { std::cout << x << std::endl; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using namespace std;

struct Node {
    int pos;
    int sum_cost;

    Node(int p, int c) {
        pos = p;
        sum_cost = c;
    }

    bool operator >(const Node &other) const {
        return sum_cost > other.sum_cost;
    }
};

struct Edge {
    int to_node;
    int cost;

    Edge(int n, int c) {
        to_node = n;
        cost = c;
    }
};

vector<vector<Edge>> adj; // 隣接行列
priority_queue<Node, vector<Node>, greater<Node>> pq; // ヒープ
int dist[10100];

int main() {
    int n; cin >> n;
    adj.resize(n);
    rep(i, n) {
        int u, k; cin >> u >> k;
        rep(j, k) {
            int v, c; cin >> v >> c;
            adj[u].emplace_back(Edge(v, c));
        }
    }

    // 初期化
    rep(i, n) {
        dist[i] = (i == 0) ? 0 : INT_INF;
        pq.push(Node(i, dist[i]));
    }

    while (!pq.empty()) {
        Node popped = pq.top();
        pq.pop();

        for (auto &edge: adj[popped.pos]) {
            Node next(edge.to_node, popped.sum_cost + edge.cost);
            if (next.sum_cost < dist[edge.to_node]) {
                pq.push(next);
                dist[edge.to_node] = next.sum_cost;
            }
        }
    }

    rep(i, n) {
        cout << i << ' ' << dist[i] << endl;
    }
}

C++: #include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
static const int M = 10000;

int n;
vector<pair<int,int> > a[M];

void dijkstra(void);

int main(){
  int x,y,z,w,i,j;

  cin >> n;
  for(i = 0;i < n;i++){
    cin >> x >> y;
    for(j = 0;j < y;j++){
      cin >> z >> w;
      a[x].push_back(make_pair(z,w));
    }
  }
  dijkstra();

  return 0;
}

void dijkstra(void){
  priority_queue<pair<int,int> > PQ;
  int color[M],d[M],i,j,x,z;

  for(i = 0;i < n;i++){
    d[i] = 10000000;
    color[i] = 0; //0=white
  }
  d[0] = 0;
  PQ.push(make_pair(0,0));
  color[0] = 1; //1=gray

  while(!PQ.empty()){
    pair<int,int>f = PQ.top(); PQ.pop();
    x = f.second;
    color[x] = 2; //2=black
    if(d[x] < f.first * (-1)) continue;

    for(j = 0;j < a[x].size();j++){
      z = a[x][j].first;
      if(color[z] == 2) continue;
      if(d[z] > d[x] + a[x][j].second){
	d[z] = d[x] + a[x][j].second;
	PQ.push(make_pair(d[z] * (-1),z));
	color[z] = 1;
      }
    }
  }
  for(i = 0;i < n;i++){
    cout << i << " " << (d[i] == 10000000 ? -1 : d[i]) << endl;
  }
}

C++: #include <stdio.h>
#include <vector>
#include <algorithm>


using namespace std;

short heap_index[10000];

struct Info{
	Info(){
		to=0;
		weight = 0;
	}
	Info(short arg_to,int arg_weight){
		to = arg_to;
		weight = arg_weight;
	}
	short to;
	int weight;
};

class InfoPQ{
public:
	InfoPQ(){
		array = new Info[10000];
		n = 0;
	}
	void push(Info arg_info){
		array[n] = arg_info;
		int tmp = n;
		while(tmp != 0 && array[tmp].weight < array[(tmp-1)/2].weight){
			std::swap(array[tmp], array[(tmp-1)/2]);
			tmp = (tmp-1)/2;
		}
		n++;
	}

	bool isEmpty(){
		return n == 0;
	}

	void writeHeapIndex(){
		for(int i=0;i<n;i++){
			heap_index[array[i].to] = i;
		}
	}

	void update(short update_index,int new_weight){
		array[heap_index[update_index]].weight = new_weight;
		int tmp = heap_index[update_index];
		while(tmp != 0 && array[tmp].weight < array[(tmp-1)/2].weight){
			std::swap(heap_index[array[tmp].to],heap_index[array[(tmp-1)/2].to]);
			std::swap(array[tmp], array[(tmp-1)/2]);
			tmp = (tmp-1)/2;
		}
	}

	Info pop(){
		Info ret = array[0];
		n--;
		heap_index[array[n].to] = 0;
		std::swap(array[0],array[n]);
		int tmp = 0;
		while(2*tmp+1 <= n-1){
			if(2*tmp+2 <= n-1){
				if(array[2*tmp+2].weight < array[tmp].weight && array[2*tmp+2].weight <= array[2*tmp+1].weight){
					std::swap(heap_index[array[tmp].to],heap_index[array[2*tmp+2].to]);
					std::swap(array[2*tmp+2],array[tmp]);
					tmp = 2*tmp+2;
				}else if(array[2*tmp+1].weight < array[tmp].weight && array[2*tmp+1].weight <= array[2*tmp+2].weight){
					std::swap(heap_index[array[tmp].to],heap_index[array[2*tmp+1].to]);
					std::swap(array[2*tmp+1],array[tmp]);
					tmp = 2*tmp+1;
				}else{
					break;
				}
			}else{
				if(array[tmp].weight > array[2*tmp+1].weight){
					std::swap(heap_index[array[tmp].to],heap_index[array[2*tmp+1].to]);
					std::swap(array[tmp],array[2*tmp+1]);
					tmp = 2*tmp+1;
				}else{
					break;
				}
			}
		}
		return ret;
	}

private:
	Info* array;
	int n;
};



int main(){
	int n,count=0,tmp,left_node,right_node,dist;
	short size;
	scanf("%d",&n);
	vector<Info> V[n];
	Info catcher;
	InfoPQ A;

	int P[n],zero_dist[n];

	for(int i=0;i<n;i++){
		P[i]=0;
		zero_dist[i] = 10000001;
	}
	zero_dist[0] = 0;
	P[0]=1;

	for(int i=0;i<n;i++){
		scanf("%d %d",&left_node,&tmp);
		if(left_node == 0){
			for(int k=0;k<tmp;k++){
				scanf("%d %d",&right_node,&dist);
				zero_dist[right_node] = dist;
			}
		}else{
			for(int k=0;k<tmp;k++){
				scanf("%d %d",&right_node,&dist);
				V[left_node].push_back(Info(right_node,dist));
			}
		}
	}

	for(short k=1;k<n;k++){
		A.push(Info(k,zero_dist[k]));
	}

	A.writeHeapIndex();

	while(count<n-1){

		catcher = A.pop();
		P[catcher.to]=1;
		count++;
		size = V[catcher.to].size();
		for(int k=0;k<size;k++){
			if(zero_dist[V[catcher.to][k].to] > catcher.weight+V[catcher.to][k].weight){
				zero_dist[V[catcher.to][k].to] = catcher.weight+V[catcher.to][k].weight;
				A.update(V[catcher.to][k].to,catcher.weight+V[catcher.to][k].weight);
			}
		}
	}

	for(int i=0;i<n;i++){
		printf("%d %d\n",i,zero_dist[i]);
	}

    return 0;
}