Go: // ダイクストラのアルゴリズム
package main

import (
	"bufio"
	"fmt"
	"log"
	"math"
	"os"
	"strconv"
	"strings"
)

type color int

const (
	white color = iota // 未訪問
	mst                // MSTとして確定
)

// 頂点
type node struct {
	num     int         // 頂点の番号
	weights map[int]int // 重みMAP
	parent  *node       // MSTへの重み最小の親
	sum     int         // 始点からの距離
	color   color
}

func (p *node) getMinToMst() int {
	if p.parent == nil {
		return math.MaxInt32
	}
	return p.weights[p.parent.num]
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	n := eGetInt(scanner)

	nodes := make([]*node, n)
	for i := 0; i < n; i++ {
		weights := eAtoi((strings.Fields(eGetline(scanner))))
		v := &node{weights[0], make(map[int]int, weights[1]), nil, 0, white}
		for j := 0; j < weights[1]; j++ {
			k := weights[j*2+2] // 相手の頂点名
			w := weights[j*2+3] // 重み
			v.weights[k] = w
		}
		nodes[i] = v
	}

	// 初回はnode[0]がMSTに入るように
	nodes[0].parent = nodes[0]

	for { // 全部チェックするまで

		// どの頂点を新たにMSTに取り込むか

		var minNode *node
		min := math.MaxInt32
		for _, v := range nodes {
			if v.color == mst {
				continue
			}
			if v.getMinToMst() < min {
				min = v.getMinToMst()
				minNode = v
			}
		}
		if minNode == nil {
			// すべて完了している.
			break
		}

		// MSTに追加する頂点決定
		minNode.color = mst
		// 自分の親の合計値と合算する
		minNode.sum = minNode.parent.sum + min

		// MSTに属していない頂点それぞれについて,MSTとの最小の重みの距離を加算
		for _, v := range nodes {
			if v.color == mst {
				continue
			}
			w, ok := v.weights[minNode.num]
			if !ok {
				// minNodeと接してない
				continue
			}

			if w < v.getMinToMst() {
				// minNodeへの距離がもっとも重みが少ないので親を変更
				v.parent = minNode
			}
		}
	}

	for i, v := range nodes {
		fmt.Printf("%d %d\n", i, v.sum)
	}
}

func eGetInt(scanner *bufio.Scanner) int {
	t := eAtoi(strings.Fields(eGetline(scanner)))
	return t[0]
}

func eGetline(p *bufio.Scanner) string {
	if !p.Scan() {
		if err := p.Err(); err != nil {
			log.Fatal(err.Error())
		}
		return ""
	}
	return p.Text()
}

func eAtoi(s []string) []int {
	ints := make([]int, len(s))
	var err error
	for i, e := range s {
		ints[i], err = strconv.Atoi(e)
		if err != nil {
			log.Fatal(err.Error())
		}
	}
	return ints
}

C++: #include<iostream>

using namespace std;

#define MAX 100

#define WHITE 0
#define GRAY 1
#define BLACK 2
#define INFTY 1<<21

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

void dijkstra(){
  for(int i=0;i<n;i++){
    color[i] = WHITE;
    p[i] = -1;
    d[i] = INFTY;
  }

  d[0] = 0;
  p[0] = -1;
  color[0] = GRAY;

  while(true){

    int minicost = INFTY;
    int u=-1;

    for(int i=0;i<n;i++){
      if(color[i] != BLACK && minicost > d[i]){
        minicost = d[i];
        u = i;
      }
    }
    if(u==-1){
      break;
    }
    color[u] = BLACK;

    for(int i=0;i<n;i++){
      if( color[i] != BLACK && d[i] > d[u] + M[u][i] ){
        d[i] = d[u] + M[u][i];
        p[i] = u;
        color[i] = GRAY;
      }
    }
  }

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

}


int main(void){
  cin >> n;
  int u,k;
  int s, t;

  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      M[i][j] = INFTY;
    }
  }

  for(int i=0;i<n;i++){
    cin >> u >> k;
    for(int j=0;j<k;j++){
      cin >> s >> t;
      M[u][s] = t;  
    }
  }

  dijkstra();

  return 0;
}

C++: #include<iostream>
#include<vector>
#include<algorithm>
#define MAX_V 100
#define INF 1e9
using namespace std;
int cost[MAX_V][MAX_V];
int d[MAX_V];
bool used[MAX_V];
int V;
void dijkstra(int s) {
	for (int i = 0; i < V; i++) {
		d[i] = INF;
		used[i] = false;
	}
	d[s] = 0;
	while (true) {
		int v = -1;
		for (int u = 0; u < V; u++) {
			if (!used[u] && ((v == -1) || d[u] < d[v])) {
				v = u;
			}
		}
		//全ての頂点が到達済み
		if (v == -1) {
			break;
		}
		//集合に新たに頂点を追加
		used[v] = true;
		for (int u = 0; u < V; u++) {
			if (cost[v][u] != -1) {
				d[u] = min(d[u], d[v] + cost[v][u]);
			}
		}
	}
}

int main() {
	for (int i = 0; i < V; i++) {
		for (int j = 0; j < V; j++) {
			cost[i][j] = -1;
		}
	}
	cin >> V;
	for (int i = 0; i < V; i++) {
		int u;
		cin >> u;
		int k;
		cin >> k;
		for (int j = 0; j < k; j++) {
			int v;
			cin >> v;
			int c;
			cin >> c;
			cost[u][v] = c;
		}
	}
	dijkstra(0);

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

C++: #include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <utility>
#include <tuple>
#include <cctype>
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define PI 4*atan(1.0)
typedef long long ll;
typedef long double ld;
using namespace std;
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
const int SIZE=200001+5000;
//int arr[SIZE]={};
//???????????§???????????¬
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(auto i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
typedef int Weight;
struct Edge {
  int src, dst;
  Weight weight;
  Edge(int src, int dst, Weight weight) :
    src(src), dst(dst), weight(weight) { }
};
bool operator < (const Edge &e, const Edge &f) {
  return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
    e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

typedef vector<Weight> Array;
typedef vector<Array> Matrix;
void shortestPath(const Graph &g, int s,
    vector<Weight> &dist, vector<int> &prev) {
  int n = g.size();
  dist.assign(n, INF); dist[s] = 0;
  prev.assign(n, -1);
  priority_queue<Edge> Q; // "e < f" <=> "e.weight > f.weight"
  for (Q.push(Edge(-2, s, 0)); !Q.empty(); ) {
    Edge e = Q.top(); Q.pop();
    if (prev[e.dst] != -1) continue;
    prev[e.dst] = e.src;
    FOR(f,g[e.dst]) {
      if (dist[f->dst] > e.weight+f->weight) {
        dist[f->dst] = e.weight+f->weight;
        Q.push(Edge(f->src, f->dst, e.weight+f->weight));
      }
    }
  }
}
vector<int> buildPath(const vector<int> &prev, int t) {
  vector<int> path;
  for (int u = t; u >= 0; u = prev[u])
    path.push_back(u);
  reverse(path.begin(), path.end());
  return path;
}
int main(){
	Graph G;
	int N;
	cin>>N;
	for(int i=0;i<N;i++){
		Edges E;
		G.push_back(E);
	}
	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;
			G[u].push_back(Edge(u,v,c));
		}
	}
	vector<Weight> dist;
	vector<int> prev;
	shortestPath(G,0,dist,prev);
	for(int i=0;i<N;i++){
		cout<<i<<" "<<dist[i]<<endl;
	}
	return 0;
}