Go: package main

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

func main() {
	r := bufio.NewReader(os.Stdin)

	var n int
	fmt.Fscan(r, &n)
	cs := make([]map[int]int, n) // []v_i -> c_i
	for h := 0; h < n; h++ {
		var u, k int
		fmt.Fscan(r, &u, &k)
		m := make(map[int]int)
		for i := 0; i < k; i++ {
			var v, c int
			fmt.Fscan(r, &v, &c)
			m[v] = c
		}

		cs[u] = m
	}

	q := make(map[int]int)
	q[0] = 0
	visited := make(map[int]struct{})
	out := make([]int, n)

	for len(q) > 0 {
		u := top(q)
		for uu, c := range cs[u] {
			// Consider the connection between u and uu.
			if _, ok := visited[uu]; ok {
				continue
			}
			if d, ok := q[uu]; !ok || d > q[u]+c {
				q[uu] = q[u] + c
			}
		}

		out[u] = q[u]
		delete(q, u)
		visited[u] = struct{}{}
	}

	for u, d := range out {
		fmt.Println(u, d)
	}
}

func top(q map[int]int) int {
	minu := -1
	min := -1
	for u, d := range q {
		if min < 0 || d < min {
			minu = u
			min = d
		}
	}

	return minu
}

C++: #include<iostream>
#define INF 100000000
#define N 101
#define W 0
#define G 1
#define B 2
using namespace std;
int n,M[N][N],d[N];
void dijkstra(int s){
  int color[N],mincost,p[N],u;
  for(int i=0;i<n;i++) color[i]=W,d[i]=INF;
  d[s]=0;
  p[s]=-1;

  while(1){
    mincost=INF;
     u=-1;    
    for(int i=0;i<n;i++)
      if(color[i]!=B && d[i]<mincost){
	mincost=d[i];
	u=i;
      }
        if(mincost==INF) break;
        color[u]=B;
    for(int i=0;i<n;i++)
      if(color[i]!=B && M[u][i]!=INF)
	if(d[u]+M[u][i]<d[i]){
	  d[i]=d[u]+M[u][i];
	  p[i]=u;
	  color[i]=G;
	}
  }
}
int main(){
  int u,k,c,v;
  cin>>n;
  for(int i=0;i<N;i++) for(int j=0;j<N;j++)M[i][j]=INF;
  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(0);
  for(int i=0;i<n;i++) cout<<i<<" "<<d[i]<<endl;
  return 0;
}

C++: #include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

#define rep(i, n) for(int i = 0; i < n; ++i)
const int max_v = 10100;
const int max_e = 505000;
const int inf = 0x3fffffff;

typedef pair<int, int> P;

typedef struct edge {
    int to, dist;
    edge():to(0),dist(0) {}
    edge(int _to, int _dist):to(_to),dist(_dist) {}
    bool operator < (const edge & o) const {
	return dist > o.dist;
    }
}edge;

struct graph {
    int V, E;
    int d[max_v], prev[max_v];
    bool vis[max_v];
    vector<edge> G[max_v];
    graph():V(0),E(0) {}

    graph(int _V):V(_V),E(0) {}

    graph(int _V, int _E, int ed[][3], bool bidirect):V(_V),E(_E) {
	rep(i, E) {
	    int u = ed[i][0], v = ed[i][1], dist = ed[i][2];
	    G[u].push_back(edge(v, dist));
	    if (bidirect) G[v].push_back(edge(v, dist));
	}
    }
    graph(int _V, int g[][max_v]) {
	V = _V; E = 0;
	rep(i, V) rep(j, V)
	    if (g[i][j] != inf) {
		G[i].push_back(edge(j, g[i][j]));
		++E;
	    }
    }

    void add_edge(int u, int v, int c) {
	G[u].push_back(edge(v, c));
    }

    void output() {
	rep(i, V) {
	    printf("[%d] ", i);
	    rep(j, G[i].size()) {
		printf("(%d %d) ", G[i][j].to, G[i][j].dist);
	    }
	    putchar('\n');
	}
    }

    void dijkstra(int g[][max_v], int s) {
	rep(i, V) d[i] = inf;
	rep(i, V) prev[i] = -1;
	rep(i, V) vis[i] = false;

	d[s] = 0;
	rep(i, V) {
	    int tmp = inf;
	    int u = -1;
	    rep(j, V) {
		if(!vis[j] && d[j] < tmp) {
		    tmp = d[j];
		    u = j;
		}
	    }
	    vis[u] = true;
	    rep(j, V) {
		if(!vis[j] && d[u] + g[u][j] < d[j]) {
		    d[j] = d[u] + g[u][j];
		    prev[j] = u;
		}
	    }
	}
    }

    void dijkstra(int s) {
	rep(i, V) d[i] = inf;
	rep(i, V) prev[i] = -1;
	rep(i, V) vis[i] = false;
	
	priority_queue<edge> pq;
	pq.push(edge(s, 0));
	d[s] = 0;

	while(! pq.empty()) {
	    edge e = pq.top(); pq.pop();
	    if(e.dist > d[e.to]) continue;
	    d[e.to] = e.dist;
	    vis[e.to] = true;
	    
	    rep(j, G[e.to].size()) {
		int v = G[e.to][j].to;
		int dist = G[e.to][j].dist;

		if(!vis[v] && d[e.to] + dist < d[v]) {
		    d[v] = d[e.to] + dist;
		    prev[v] = e.to;
		    pq.push(edge(v, d[v]));
		}
	    }
	}
    }
};

int N, M;

void solve() {
    int u, k, v, c;
    scanf("%d", &N);
    graph g = graph(N);
    rep(i, N) {
	scanf("%d%d", &u, &k);
	rep(j, k) {
	    scanf("%d%d", &v, &c);
	    g.add_edge(u, v, c);
	}
    }
    g.dijkstra(0);
    rep(i, N) {
	printf("%d %d\n", i, g.d[i]);
    }
}

int main() {
    solve();
    return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;

const int MAX=105;
int state[MAX],N,D[MAX];
vector<pair<int,int>> S[MAX];
priority_queue<pair<int,int>> Q;

void dijkstra(){
    int cnt=1;
    for(int i=0;i<N;i++){
        state[i]=0;
        D[i]=100000000;
    }
    state[0]=1;
    D[0]=0;
    for(int i=0;i<S[0].size();i++){
        Q.push(make_pair(-S[0][i].second,S[0][i].first));
        D[S[0][i].first]=min(D[S[0][i].first],D[0]+S[0][i].second);
    }
    while(1){
        int a=Q.top().second;
        cout<<a<<endl;
        if(state[a]==0){
            Q.pop();
            state[a]=1;
            cnt++;
            for(int i=0;i<S[a].size();i++){
                if(state[S[a][i].first]==0){
                    Q.push(make_pair(-S[a][i].second,S[a][i].first));
                    D[S[a][i].first]=min(D[S[a][i].first],D[a]+S[a][i].second);
                }
            }
        }
        else Q.pop();
        if(cnt==N) break;
    }
    return;
}


int main(){
    
    cin>>N;
    for(int i=0;i<N;i++){
        int l,a;cin>>l>>a;
        for(int j=0;j<a;j++){
            int b,c;cin>>b>>c;
            S[i].push_back(make_pair(b,c));
        }
    }
    dijkstra();
    for(int i=0;i<N;i++){
        cout<<i<<" "<<D[i]<<endl;
    }
}

C++: #include <iostream>
#define rep(i,N) for(int i = 0; i<(int)(N); i++)
#define REP(i,k,N) for(int i = k; i<(int)(N); i++)
#define INF 100000+1
typedef long long ll;
using namespace std;

int main(){
        int n;
        cin >> n;
        int d[100][100];
        rep(i,100) rep(j,100) d[i][j]=INF;

        int u,k,v,c;
        rep(i,n){
                cin >> u >>k;
                rep(j,k){
                        cin >> v >> c;
                        d[u][v] = c;
                }
        }

        ll l[100];
        rep(i,n) l[i]=INF*n;
        l[0]=0;
        bool update = true;
        while(update) {
                update  = false;
                rep(from,n) {
                        if(l[from] == INF*n) continue;
                        rep(to,n){
                                if(from == to) continue;

                                if(l[to] > l[from]+d[from][to]) {
                                        update = true;
                                        l[to] = l[from]+d[from][to];
                                }

                        }
                }
        }
        rep(i,n){
                cout << i << " " << l[i] << endl;
        }

        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() {   
	cin >> V;
	for (int i = 0; i < V; i++) {     
		for (int j = 0; j < V; j++) { 
			cost[i][j] = -1;               
		}                                 
	}                                      
	
	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;
}