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;

int main()
{
    int n, m, i, j, a, w;
    int* adj[100];
    int* dist[100];
    cin >> n;
    for(i = 0; i < n; i++){
        cin >> i >> m;
        adj[i] = new int [m + 1];
        dist[i] = new int [m + 1];
        for(j = 0; j < m; j++){
            cin >> a >> w;
            adj[i][j] = a;
            dist[i][j] = w;
        }
        adj[i][m] = -1;
        dist[i][m] = -1;
    }
    int *d, *prev, *Q;
    d = new int [n];
    prev = new int [n];
    Q = new int [n];
    for(i = 0; i < n; i++){ d[i] = 200000; prev[i] = -1; Q[i] = i; }
    int rest = n;
 
    int u, v, min;
    d[0] = 0;
    while(rest > 0){
        min = 200000;
        for(i = 0; i < n; i++){
            if(min > d[i] && Q[i] >= 0){ min = d[i]; u = i; }
        }
        Q[u] = -1;
        rest--;

        for(j = 0; adj[u][j] >= 0; j++){
            v = adj[u][j];
            if(d[v] > d[u] + dist[u][j]){
                d[v] = d[u] + dist[u][j];
                prev[v] = u;
            }
        }
    };
    for(i = 0; i < n; i++){ cout << i << " " << d[i] << endl; }
    for(i = 0; i < n; i++){
        delete adj[i]; delete dist[i]; }
    delete d;
    delete prev;
    delete Q;
    cin >> n;
 
    return 0;
}

C++: #include<iostream>
#include<algorithm>
#include<vector>
#define MAX 101
#define INF 100001
using namespace std;

int n, isSelected[MAX], dist[MAX];
vector<pair<int, int>> ver[MAX];

void initDijkstra(void);
void dijkstra(void);
bool doesFinished(void);

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

	initDijkstra();

	while (!doesFinished())dijkstra();

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

	return 0;
}

void initDijkstra(void) {

	dist[0] = 0;
	isSelected[0] = 1;
	for (int i = 1; i <= n; i++)dist[i] = INF;

	vector<pair<int, int>>::iterator itv;

	for (itv = ver[0].begin(); itv != ver[0].end(); itv++) {
		dist[itv->first] = itv->second;
	}

}

void dijkstra(void) {
	int i, minu, mindist = INF;
	vector<pair<int, int>>::iterator itv;

	for (i = 0; i < n; i++) {
		if (isSelected[i] == 0)continue;
		for (itv = ver[i].begin(); itv != ver[i].end(); itv++){
			if (isSelected[itv->first] == 1)continue;
			if (itv->second < mindist) {
				mindist = itv->second;
				minu = itv->first;
			}
		}
	}
	isSelected[minu] = 1;
	//dist[minu] = dist[minp] + mindist;
	for (itv = ver[minu].begin(); itv != ver[minu].end(); itv++) {
		if (isSelected[itv->first] == 1)continue;
		dist[itv->first] = min(dist[minu] + itv->second, dist[itv->first]);
	}
}

bool doesFinished(void) {
	for (int i = 0; i < n; i++) {
		if (isSelected[i] == 0)return false;
	}
	return true;
}

C++: #include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;
#define MAX 10000000

int b[110];

int solve(int a[110][110], int n){
	b[0] = 0;
	for(int i = 0;i < n;i++){
		for(int j = 1;j < n;j++){
			//if(j == 4)cout << b[4] << i << " " << endl;
			if(a[i][j] != -1)b[j] = min(b[j], a[i][j]+b[i]);
			//if(j == 4)cout << b[4] << i << " " << endl;
		}
	}
	//cout << endl;
	return 0;
}

int main(){
	int a[110][110], n;
	fill((int*)a, (int*)(a+110), -1);
	fill(b, b+110, MAX);
	cin >> n;
	for(int i = 0;i < n;i++){
		int u, k, c, d;
		cin >> u >> k;
		for(int j = 0;j < k;j++){
			cin >> c >> d;
			a[u][c] = a[c][u] = d;
		}
	}
	for(int i = 0;i < n;i++)solve(a, n);
	for(int i = 0;i < n;i++){
		cout << i << " " << b[i] << endl;
	}
	
	return 0;
}
/*
5
0 3 2 3 3 1 1 2
1 2 0 2 3 4
2 3 0 3 3 1 4 1
3 4 2 1 0 1 1 4 4 3
4 2 2 1 3 3
*/

C++: #include <iostream>

using namespace std;
int n;
int dat[100][100];
int cost[100];
int done[100];

void prim(){
	for(int i=0;i<n;i++){
		cost[i]=1<<21;
		done[i]=0;
	}
	int s=0;	
	int next, ncost=1<<21;
	done[s]=1;
	cost[s]=0;
	while(1){
		ncost=1<<21;
		for(int j=0;j<n;j++){
			if(done[j]){
				for(int i=0;i<n;i++){
					if(dat[j][i]!=-1){
						if(cost[i]>=dat[j][i]&&!done[i]){
							cost[i]=dat[j][i];
						}
						if(ncost>cost[i]&&!done[i]){
							next=i;
							ncost=cost[i];
						}
					}
				}
			}
		}
//		cout<<"next:"<<next<<" cost:"<<cost[next]<<endl;
		done[next]=1;
		int flag=true;
		for(int i=0;i<n;i++){
			if(!done[i]) flag = false;
		}
		if(flag)
			return;
	}
}


void dijk(){
	for(int i=0;i<n;i++){
		cost[i]=1<<21;
		done[i]=0;
	}
	int s=0;	
	int next, ncost=1<<21;
	done[s]=1;
	cost[s]=0;
	while(1){
		ncost=1<<21;
		for(int j=0;j<n;j++){
			if(done[j]){
				for(int i=0;i<n;i++){
					if(dat[j][i]!=0){
						if(cost[i]>=dat[j][i]+cost[j]){
							cost[i]=dat[j][i]+cost[j];
						}
						if(ncost>cost[i]&&!done[i]){
							next=i;
							ncost=cost[i];
						}
					}
				}
			}
		}
//		cout<<"next:"<<next<<" cost:"<<cost[next]<<endl;
		done[next]=1;
		int flag=true;
		for(int i=0;i<n;i++){
			if(!done[i]) flag = false;
		}
		if(flag)
			return;
	}
}


int main(){
	int num, from, dist, c;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>from>>num;
		for(int j=0;j<num;j++){
			cin>>dist>>c;
			dat[from][dist]=c;
		}
	}
	dijk();
	for(int i=0;i<n;i++){
		cout<<i<<" "<<cost[i]<<endl;
	}
	return 0;
}