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>
using namespace std;
static const int MAX =100;
static const int INFTY =(1<<21);
static const int WHITE =0;
static const int GRAY =1;
static const int BLACK =2;

int n, M[MAX][MAX];

int dijkstra(){
  int minv;
  int d[MAX],color[MAX];

  for(int i=0;i<n;i++){
    d[i]=INFTY;
    color[i]=WHITE;
  }
  d[0]=0;
  color[0]=GRAY;
  while(1){
    minv=INFTY;
    int u=-1;
    for(int i=0;i<n;i++){
      if(minv>d[i] && color[i] !=BLACK){
        u=i;
        minv=d[i];
      }
    }
    if(u==-1)break;
    color[u]=BLACK;
    for(int v=0;v<n;v++){
      if(color[v] != BLACK && M[u][v]!=INFTY){
        if(d[v]> d[u]+M[u][v]){
          d[v]=d[u]+M[u][v];
          color[v]=GRAY;
        }
      }
    }
  }
  for(int i=0;i<n;i++){
    cout << i << " " << (d[i]==INFTY? -1:d[i]) << endl;
  }
}

int main(){
  cin >> n;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      M[i][j]=INFTY;
    }
  }
  int k,c,u,v;
  for(int i=0;i<n;i++){
    cin >> u >> k;
    for(int j=0;j<k;j++){
      cin >> v >> c;
      M[u][v]=c;
    }
  }

  dijkstra();
  return 0;
}

C++: #include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int num = 10000, num1 = 500000, INF = 20000000;
int n, d[num], c[num];
vector<pair<int, int>> v[num];
priority_queue<pair<int, int>> q;
inline void mini() {
	q.push(make_pair(0, 0));
	while (!q.empty()) {
		pair<int, int> p = q.top(); q.pop();
		int a = p.second;
		c[a] = 1;
		for (int i = 0; i < v[a].size(); i++) {
			int b = v[a][i].first;
			if (c[b] == 0 && d[b] > d[a] + v[a][i].second) {
				d[b] = d[a] + v[a][i].second;
				q.push(make_pair(d[b] * -1, b));
			}
		}
	}
		
}
int main() {
	int u, k, s, t;
	cin >> n;
	for (int i = 1; i < n; i++) {
		d[i] = INF;
		c[i] = 0;
	}
	d[0] = 0;
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &u, &k);
		for (int j = 0; j < k; j++) {
			scanf("%d%d", &s, &t);
			v[u].push_back(make_pair(s, t));
		}
	}
	mini();
	for (int i = 0; i < n; i++) {
		printf("%d %d\n", i, d[i]);
	}
	return 0;
}

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

int main() {
    int n;
    cin >> n;

    int a[n][n];
    int done[n]; // -1: まだ ソレ以外: 確定距離
    for (int i = 0; i < n; ++i) {
        done[i] = -1;
        for (int j = 0; j < n; ++j) {
            a[i][j] = -1;
        }
    }
    for (int i = 0; i < n; ++i) {
        int u, k;
        cin >> u >> k;
        for (int j = 0; j < k; ++j) {
            int v, c;
            cin >> v >> c;
            a[i][v] = c;
        }
    }

    // デバッグ用
//     for (int i = 0; i < n; ++i) {
//         for (int j = 0; j < n; ++j) {
//             cout << i << " " << j << " " << a[i][j] << endl;
//         }
//     }

    // 最初は0が確定済みのノードとなる
    done[0] = 0;

    // 確定済みのノードから行ける、未到達の最小のノードを探す
    // その最小のノードは次の確定済みとする...
    // とりあえずデバッグがてら10回す (最終的にwhileにして条件で対応する)
    // 全てdoneになったら終了
    for (int r = 0; r < n-1; ++r) {
        int next_node = -1;
        int next_cost = 1000000;
        for (int i = 0; i < n; ++i) {
            if (done[i] == -1) {
                // 未確定であれば何もしない
                continue;
            }

            for (int j = 0; j < n; ++j) {
                // 到達済みは見ない
                if (done[j] != -1) {
                    continue;
                }

                // コストが-1なら到達できない
                if (a[i][j] == -1) {
                    continue;
                }
                
                if (done[i] > next_cost) {
                    continue;
                }
                
                // 行けるところのコスト (iまでの距離+そこからの距離) を探す
//                cout << "src:" << i << " dst:" << j << " cost:" << a[i][j] << " total:" << done[i] + a[i][j] << endl;

                // 今のnext_costよりもtotalcostが小さければ、次のノードにしたい
                if ((done[i] + a[i][j]) < next_cost) {
                    next_cost = done[i] + a[i][j];
                    next_node = j;
                }
            }
        }
//        cout << "iter:" << r << endl;
//        cout << "next_node:" << next_node << endl;
//        cout << "next_cost:" << next_cost << endl;
        done[next_node] = next_cost;
    }

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

    return 0;
}

C++: //
//  main.cpp
//
//
//  Created by ???????????? on 2017/10/23.
//  Copyright ?? 2017 ????????????. All rights reserved.
//

#include <iostream>
#include <stdio.h>
#include <queue>
#include <algorithm>


#define n_max 100
#define WHITE 0
#define GRAY 1
#define BLACK 2
#define INFTY (1<<20)

using namespace std;

int n, M[n_max][n_max], color[n_max], d[n_max], p[n_max];

void init(){
    int i, j, id, num, node;
    scanf("%d", &n);
    for(i = 0; i < n; i++){
        for(j = 0; j < n; j++){
            M[i][j] = INFTY;
        }
    }
    
    
    for(i = 0; i < n; i++){
        scanf("%d %d", &id, &num);
        for(j = 0; j < num; j++){
            scanf("%d", &node);
            scanf("%d", &M[id][node]);
        }
        color[i] = WHITE;
        d[i] = INFTY;
    }
}

void dijkstra(){
    //initializing
    d[0] = 0;
    p[0] = -1;
    
    priority_queue<pair<int, int>> PQ;
    
    PQ.push(make_pair(0, 0));
    
    int u;
    while(!PQ.empty()){
        int mincost = INFTY;
        //first weight, second idx
        pair<int, int> f= PQ.top(); PQ.pop();
        u = f.second;
        color[u] = BLACK;
        
        if(d[u] < f.first*(-1)) continue;
        
        for(int v = 0; v < n; v++){
            if((color[v] != BLACK) && (M[u][v] != INFTY)){
                if((d[u] + M[u][v]) < d[v]){
                    d[v] = M[u][v] + d[u];
//                    p[v] = u;
                    PQ.push(make_pair(d[v]*(-1), v));
                    color[v] = GRAY;
                }
            }
        }
    }
    for(int i = 0; i < n; i++){
        cout<<i<<" "<<d[i]<<endl;
    }
}

int main(int argc, const char * argv[]) {
    init();
    dijkstra();
    //    std::cout << "Hello, World!\n";
    return 0;
}