Go: package main

import (
	"fmt"
	"os"
	"bufio"
	"strings"
	"strconv"
)
var MAX = 1000000
type Vertex struct{
	Value int
	Routes map[int]int
	Done bool
}
func NewVertex(value int) *Vertex{
	routes := make(map[int]int)
	// for i, _ := range routes {
	// 	routes[i] = MAX
	// }
	return &Vertex{ value, routes, false }
}

func (v *Vertex) SetRoute(key, weight int) {
	v.Routes[key] = weight
}

type Path struct {
	Key int
	Weight int
}

var count = 0
func ShortestRoutes(list []*Vertex) []int {
	// create result table
	result  := make([]int, len(list))
	// fmt.Println(result)
	for i, _ := range result {
		result[i] = MAX
	}

	queue := make([]Path, 0)
	queue = append(queue, Path{0, 0})
	result[0] = 0

	for len(queue) != 0 {
		count++
		path := queue[0]
		queue = queue[1:]
		for key, weight := range list[path.Key].Routes {
			// fmt.Println(list[path.Key].Routes)
			// set to result
			// fmt.Printf("Path(%d, %d) ? result[%d] => %d, wieght: %d\n", path.Key, path.Weight, key, result[key], weight)
			if path.Weight + weight < result[key] {
				result[key] = path.Weight + weight 
				queue = append(queue, Path{key, result[key]})
			// } else if !list[key].Done {
			// 	queue = append(queue, Path{key, result[key]})
			}
		}
		list[path.Key].Done = true
	}
	return result
}
func main() {
	var n int
	fmt.Scanf("%d", &n)
	list := make([]*Vertex, n)
	scanner := bufio.NewScanner(os.Stdin)
	for i := 0; i < n; i++ {
		scanner.Scan()
		elements := strings.Split(scanner.Text(), " ")
		value, _ := strconv.Atoi(elements[0])
		list[i] = NewVertex(value)
		for j := 2; j < len(elements); j += 2 {
			key, _    := strconv.Atoi(elements[j])
			weight, _ := strconv.Atoi(elements[j + 1])
			list[i].SetRoute(key, weight)
		}
	}

	result := ShortestRoutes(list)
	for i := 0; i < len(result); i++ {
		fmt.Printf("%d %d\n", i, result[i]);
	}
	// fmt.Printf("count: %d\n", count)
}

C++: #include<iostream>
#include<queue>
#include<vector>
#define MAX 10000
#define INFTY 1<<21
#define WHITE 0
#define GRAY 1
#define BLACK 2
using namespace std;

vector<pair<int, int> > adj[MAX];   // <頂点,重み>
priority_queue<pair<int, int> > PQ; // <重み,頂点> 正確には重み×-1
int d[MAX], color[MAX];
int n;

// ダイクストラのアルゴリズムに優先度付きキューを用いて、
// 最短経路上の各頂点まで道のりを求めて出力する。
void dijkstra()
{
	for (int i = 0; i < n; i++)
	{
		d[i] = INFTY;
		color[i] = WHITE;
	}

	d[0] = 0;
	color[0] = GRAY;
	PQ.push(make_pair(0, 0));

	while (!PQ.empty())
	{
		pair<int, int> f = PQ.top(); PQ.pop();
		int u = f.second;

		if (d[u] < f.first * (-1)) continue;

		color[u] = BLACK;

		for (int i = 0; i < adj[u].size(); i++)
		{
			int v = adj[u][i].first;

			if (color[v] == BLACK) continue;

			if (d[u] + adj[u][i].second < d[v])
			{
				d[v] = d[u] + adj[u][i].second;
				PQ.push(make_pair(d[v] * (-1), v));
				color[v] = GRAY;
			}
		}
	}

	for (int i = 0; i < n; i++)
	{
		int x = (d[i] == INFTY) ? -1 : d[i];
		cout << i << " " << x << endl;
	}
}

int main()
{
	cin >> n;

	int k, u, v, c;
	for (int i = 0; i < n; i++)
	{
		cin >> u >> k;
		for (int j = 0; j < k; j++)
		{
			cin >> v >> c;
			adj[u].push_back(make_pair(v, c));
		}
	}

	dijkstra();

	return 0;
}

// 参考
// 本P310掲載の重み付き有向グラフの作成
void testSample()
{
	n = 7;
	adj[0].push_back(make_pair(1, 6));
	adj[0].push_back(make_pair(2, 12));
	adj[0].push_back(make_pair(3, 7));
	adj[2].push_back(make_pair(2, 8));
	adj[3].push_back(make_pair(4, 3));
	adj[3].push_back(make_pair(5, 53));
	adj[4].push_back(make_pair(3, 1));
	adj[4].push_back(make_pair(5, 0));
}

C++: #include<bits/stdc++.h>
#define d first
#define wgt first
#define to second

using namespace std;

typedef pair<int,int> pii;
typedef vector<pii> vec;
typedef vector<vec> Graph;

Graph G(11000);
int n,d[11000];

void Dijkstra()
{
	bool used[1100];
	priority_queue<pii,vector<pii>,greater<pii> > pq;
	fill(d,d+n,INT_MAX);
	memset(used,false,sizeof(used));
	pq.push(make_pair(0,0));
	while(!pq.empty())
	{
		pii u=pq.top();pq.pop();
		if(used[u.to]) continue;
		used[u.to]=true;
		d[u.to]=u.d;
		for(int i=0;i<G[u.to].size();i++)
			if(d[G[u.to][i].to]>d[u.to]+G[u.to][i].wgt)
			{
				d[G[u.to][i].to]=d[u.to]+G[u.to][i].wgt;
				pq.push(make_pair(d[G[u.to][i].to],G[u.to][i].to));
			}
	}
}

int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		int u,t;
		scanf("%d%d",&u,&t);
		for(int j=0;j<t;j++)
		{
			int v,w;
			scanf("%d%d",&v,&w);
			G[u].push_back(make_pair(w,v));
		}
	}
	Dijkstra();
	for(int i=0;i<n;i++)
		printf("%d %d\n",i,d[i]);
	return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;

#define INF (1 << 30)

struct edge{

  int cost, to;

};

struct state{

  int node, cost;
  bool operator <(const state &b)const{
    return cost > b.cost;
  }
};

int n;
int d[10001];
vector<edge> glaph[10001];
priority_queue<state> qu;

void sss(){

  fill(d,d+10001,INF);
  qu.push((state){0,0});
  d[0] = 0;

  while(!qu.empty()){

    state info;
    info = qu.top();
    qu.pop();

    for(int i = 0; i < (double)glaph[info.node].size(); i++){
      if(d[glaph[info.node][i].to] > glaph[info.node][i].cost + d[info.node]){
      d[glaph[info.node][i].to] = glaph[info.node][i].cost + d[info.node];
      qu.push((state){glaph[info.node][i].to,d[info.node]}); 
      }
	}
  }

  for(int i = 0; i < n; i++){
    cout << i << " " << d[i] << endl;
  }
  



}

int main(){

  cin >> n;

  for(int i = 0; i < n; i++){
    int k, v, c, u;
    cin >> u >> k;
    for(int j = 0; j < k; j++){
      cin >> v >> c;
      glaph[u].push_back((edge){c,v});
    }
  }

  sss();


}

C++: #include <cstdio>
#include <queue>
#include <algorithm>

#define rep(i, n) for(int i = 0; i < (n); ++i)

using namespace std;

const int inf = 1e9;

typedef pair<int, int> P;

struct E{
	E(int t, int c): t(t), c(c){} 

	int t, c;
};

int n;
vector<E> g[10000];
int d[10000];

int main(){
	scanf("%d", &n);
	rep(i, n){
		int u, k;
		scanf("%d%d", &u, &k);
		rep(j, k){
			int v, c;
			scanf("%d%d", &v, &c);
			g[u].push_back(E(v, c));
		}
	}

	fill_n(d, n, inf);

	priority_queue<P, vector<P>, greater<P> > q;
	d[0] = 0;
	q.push(P(0, 0));
	while(!q.empty()){
		P v = q.top();
		q.pop();
		if(v.first > d[v.second]){
			continue;
		}
		rep(i, g[v.second].size()){
			E e = g[v.second][i];
			if(d[e.t] > v.first + e.c){
				d[e.t] = v.first + e.c;
				q.push(P(d[e.t], e.t));
			}
		}
	}

	rep(i, n){
		printf("%d %d\n", i, d[i]);
	}
	return 0;
}

C++: #include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <functional>
#include <map>
#include <set>
#include <cmath>
#include <string>
#define SIZE 10005
#define INF 10000005

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

int V;
ll K;

struct edge{int to,cost;};
vector<edge> G[SIZE];
int d[SIZE];

void dijkstra(int s){
	priority_queue<P, vector<P>, greater<P>> que;
	fill(d,d+V,INF);
	d[s] = 0;
	que.push(P(0,s));

	while(!que.empty()){
		P p = que.top();que.pop();
		int v = p.second;
		if(d[v] < p.first)continue;
		for(int i=0;i<G[v].size();i++){
			edge e = G[v][i];
			if(d[e.to] > d[v] + e.cost){
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to],e.to));
			}
		}
	}
}

int main()
{
	scanf("%d",&V);
	int u,k,v,c;
	for(int i=0;i<V;i++){
		scanf("%d%d",&u,&k);
		for(int j=0;j<k;j++){
			scanf("%d%d",&v,&c);
			G[u].push_back((edge){v,c});
		}
	}
	dijkstra(0);
	for(int i=0;i<V;i++){
		printf("%d %d\n",i,d[i]);
	}
	return 0;
}