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<bits/stdc++.h>
using namespace std;
static const int MAX = 100; 
int n,M[MAX][MAX];
void dij(){
	int minv;
	int d[MAX],color[MAX];
	for(int i = 0;i < n;i++){
		d[i] = INT_MAX;
		color[i] = 0;
	}
	d[0] = 0;
	color[0] = 1;
	while(1){
		minv = INT_MAX;
		int u = -1;
		for(int i = 0;i < n;i++){
			if(minv > d[i] && color[i] != 2){
				u = i;
				minv = d[i];
			}
		}
		if(u == -1)break;
		color[u] = 2;
		for(int v = 0; v < n; v++){
			if(color[v] != 2 && M[u][v] != INT_MAX){
				if(d[v] > d[u] + M[u][v]){
					d[v] = d[u] + M[u][v];
					color[v] = 1;
				}
			}
		}
	}
	for(int i = 0;i < n;i++){
		cout << i << " " << (d[i] == INT_MAX ? -1 : d[i]) << endl;
	}
}
int main(){
	cin >> n;
	for(int i = 0;i < n;i++){
		for(int k = 0;k < n;k++){
			M[i][k] = INT_MAX;
		}
	}
	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;
		}
	}
	dij();
}

C++: #include<iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
using P = pair<int,int>;

/* 大文字を小文字に変換 */
char tolower(char c) {return (c + 0x20);}
/* 小文字を大文字に変換 */
char toupr(char c) {return (c - 0x20);}

// if('A'<=s[i] && s[i]<='Z') s[i] += 'a'-'A';

/*
string s = "abcdefg"
s.substr(4) "efg"
s.substr(0,3) "abc"
s.substr(2,4) "cdef"

// イテレータ要素のインデックス
distance(A.begin(), itr);
*/

const int MAX_N = 105, INF = 1001001000;
const int WHITE = 0, GRAY = 1, BLACK = 2;

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

void init(){
    rep(i,n){
        rep(j,n) M[i][j] = -1;
        color[i] = WHITE;
        d[i] = INF;
    }
}

void dijkstra(int u){
    d[u] = 0;
    p[u] = -1;
    while(true){
        // 第一段階：次に更新する辺を決定する
        int mincost = INF;
        rep(i,n){
            if(color[i] != BLACK && mincost > d[i]){
                mincost = d[i];
                u = i;
            }
        }
        if(mincost == INF) break;   // 全ての辺の最小コストが無限大であることはないので、全ての頂点のcolorがBLACKになったということ
        color[u] = BLACK;   // 現時点で最短経路木に含まれない中で最短のものを最短経路木に含める
        // 第二段階:ただいま最短経路木に含めた頂点に隣接する頂点への最短経路を更新する
        rep(v,n){
            if(color[v] != BLACK && M[u][v] != -1){
                if(d[v] > M[u][v] + d[u]){
                    d[v] = M[u][v] + d[u];
                    p[v] = u;
                    color[v] = GRAY;
                }
            }
        }
    }
}

int main()
{
    cin >> n;
    init();
    rep(i,n){
        int u; cin >> u;
        int k; cin >> k;
        rep(_,k){
            int v,c; cin >> v >> c;
            M[u][v] = c;
        }
    }
    dijkstra(0);
    rep(i,n){
        printf("%d %d\n", i, d[i]);
    }
}

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

static const int MAX=100;
static const int WHITE=0;
static const int GRAY=1;
static const int BLACK=2;

int n,M[MAX][MAX];

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

  for(int i=0;i<n;i++){
    d[i]=INT_MAX;
    color[i]=WHITE;
  }

  d[0]=0;
  color[0]=GRAY;
  
  while(1){
    int u=-1;  
    mincost=INT_MAX;

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

    if(mincost==INT_MAX) break;

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

int main(){
  cin>>n;

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

  int u,k,v,c;
  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>
using namespace std;

#define N 101
#define INF 500001 
int n;

int A[N][N];
int color[N];
int d[N];

void dijkstra(int root) {
    d[root] = 0;

    while(true) {
        int added = -1;
        int minw = INF;
        for (int i = 0; i < n; i++) {
            if (color[i] == 0 && d[i] < minw) {
                added = i;
                minw = d[i];
            }
        }

        if (added == -1) {
            break;
        }

        color[added] = 1;
        for (int i = 0; i < n; i++) {
            if (color[i] == 0 && (d[added] + A[added][i]) < d[i]) {
                d[i] = d[added] + A[added][i];
            }
        }
    }
}

int main() {
    cin >> n;

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

    int w;
    int node;
    int k;
    int ad;
    for (int i = 0; i < n; i++) {
        color[i] = 0;
        d[i] = INF;

        cin >> node >> k;
        for (int j = 0; j < k; j++) {
            cin >> ad >> w;
            A[i][ad] = w;
        }
    }

    dijkstra(0);

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

    return 0;
}