Go: package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

const T = 10000000

var n int
var A [101][101]int

func nextInt() int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}
func Shortestsearch() {
	var Minimum int
	var d, color [100]int
	var u int

	for i := 0; i < n; i++ {
		d[i] = T
		color[i] = 0
	}

	d[0] = 0
	color[0] = 1

	for {
		Minimum = T
		u = -1
		for i := 0; i < n; i++ {
			if Minimum > d[i] && color[i] != 2 {
				u = i
				Minimum = d[i]
			}
		}
		if u == -1 {
			break
		}
		color[u] = 2
		for j := 0; j < n; j++ {
			if color[j] != 2 && A[u][j] != T {
				if d[j] > d[u]+A[u][j] {
					d[j] = d[u] + A[u][j]
					color[j] = 1
				}
			}
		}
	}
	for i := 0; i < n; i++ {
		fmt.Printf("%d %d\n", i, d[i])
	}
}
func main() {
	sc.Split(bufio.ScanWords)
	n = nextInt()

	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			A[i][j] = T
		}
	}
	for i := 0; i < n; i++ {
		u := nextInt()
		k := nextInt()
		for j := 0; j < k; j++ {
			v := nextInt()
			c := nextInt()
			A[u][v] = c
		}
	}
	Shortestsearch()
}

C++: #include <cstdio>
static const int INFTY = (1 << 21);
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

int n, **M;
int *d, *p;

void dijkstra() {
    int u, minv;
    int d[n], p[n], color[n];

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

    while (1) {
        u = -1;
        minv = INFTY;
        for (int i = 0; i < n; i++) {
            if (color[i] != BLACK && d[i] < minv) {
                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) {
                // printf("d[%d] = %d, M[%d][%d] = %d, d[%d] = %d\n", u, d[u], u, v, M[u][v], v, d[v]);
                if (d[u] + M[u][v] < d[v]) {
                    p[v] = u;
                    d[v] = d[u] + M[u][v];
                    color[v] = GRAY;
                }             
            }
        }
    }
    
    for (int i = 0; i < n; i++) {
        printf("%d %d\n", i, d[i]);
    }
}

int main() {
    scanf("%d", &n);

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

    for (int i = 0; i < n; i++) {
        int u, k;
        scanf("%d %d", &u, &k);
        for (int j = 0; j < k; j++) {
            int v, c;
            scanf("%d %d", &v, &c);
            M[u][v] = c;
            printf("");
        }
    }

    dijkstra();

    return 0;
}

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;
}