Go: package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
	"strconv"
)

const NIL = -1

type Node struct {
	id     int
	weight int
}

func init() {
	sc.Split(bufio.ScanWords)
}

type NodeHeap []Node

func (h NodeHeap) Len() int           { return len(h) }
func (h NodeHeap) Less(i, j int) bool { return h[i].weight < h[j].weight }
func (h NodeHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *NodeHeap) Push(x interface{}) {
	*h = append(*h, x.(Node))
}

func (h *NodeHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	num, _ := strconv.Atoi(scanString())
	return num
}

func scanString() string {
	sc.Scan()
	return sc.Text()
}

func init() {
	sc.Split(bufio.ScanWords)
}

func main() {
	n := scanInt()

	list := make([][]int, n)
	weight := make([]int, n)
	for i := range list {
		list[i] = make([]int, n)
		weight[i] = NIL
		for j := range list[i] {
			list[i][j] = NIL
		}
	}

	for i := 0; i < n; i++ {
		u := scanInt()
		k := scanInt()
		for j := 0; j < k; j++ {
			v := scanInt()
			w := scanInt()
			list[u][v] = w
		}
	}

	start := Node{id: 0, weight: 0}
	h := &NodeHeap{start}
	heap.Init(h)

	for h.Len() > 0 {
		node := heap.Pop(h).(Node)
		if weight[node.id] != NIL {
			continue
		}
		weight[node.id] = node.weight

		for i, w := range list[node.id] {
			if w == NIL {
				continue
			}
			heap.Push(h, Node{id: i, weight: w + node.weight})
		}
	}

	w := bufio.NewWriter(os.Stdout)
	for i := 0; i < n; i++ {
		fmt.Fprint(w, i)
		fmt.Fprint(w, " ")
		fmt.Fprint(w, weight[i])
		fmt.Fprintln(w)
	}
	w.Flush()
}

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

C++: #include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e16;
const ll mod = 1000000007;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
template<class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
int ctoi(char c) {
  if (c >= '0' && c <= '9') {
    return c - '0';
  }
  return 0;
}
ll factorial(ll n) {
  if (n == 1) {
    return 1;
  }
  ll ans = factorial(n-1);
  return ans*n;
}
ll gcd(ll a, ll b) {
  if (a < b) {
    ll tmp = a;
    a = b;
    b = tmp;
  }
  ll r = a%b;
  while(r != 0) {
    a = b;
    b = r;
    r = a%b;
  }
  return b;
}
ll lcm(ll a, ll b) {
  return (a/gcd(a, b))*b;
}
bool prime(ll n) {
  if (n == 1) {
    return false;
  } else {
    for (ll i = 2; i <= (ll)pow(n, 0.5); i++) {
      if (n%i == 0) return false;
    }
  }
  return true;
}
ll RepeatSquaring(ll n, ll p, ll m) {
  if (p == 0) return 1;
  if (p%2 == 0) {
    ll t = RepeatSquaring(n, p/2, m);
    return (t*t)%m;
  }
  return (n*RepeatSquaring(n, p-1, m))%m;
}

vector <ll> color(100, 0);
vector <vector <ll>> m(100, vector <ll> (100, -1));
vector <ll> d(100, INF);
vector <ll> p(100, -1);

void dijkstra(ll n) {
  d.at(0) = 0;
  p.at(0) = -1;
  while (true) {
    ll mincost = INF;
    ll u;
    rep(i, n) {
      if (color.at(i) != 2 && d.at(i) < mincost) {
        mincost = d.at(i);
        u = i;
      }
    }
    if (mincost == INF) break;
    color.at(u) = 2;
    rep(i, n) {
      if (color.at(i) != 2 && m.at(u).at(i) != -1) {
        if (d.at(u)+m.at(u).at(i) < d.at(i)) {
          d.at(i) = d.at(u) + m.at(u).at(i);
          p.at(i) = u;
          color.at(i) = 1;
        }
      }
    }
  }
  return;
}

int main() {
  ll n;
  cin >> n;
  rep(i, n) {
    ll u, k;
    cin >> u >> k;
    rep(j, k) {
      ll v, c;
      cin >> v >> c;
      m.at(i).at(v) = c;
    }
  }
  dijkstra(n);
  rep(i, n) {
    cout << i << ' ' << d.at(i) << endl;
  }
}