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>
static const int INFTY = (1<<20);
static const int MAX = 100;
static const int WHITE = 0;
static const int BLACK = 1;

int main() {
  int n;
  int M[110][110];
  int d[110];
  int visited[110];
  std::cin >> n;
  for(int i=0; i<n; ++i) {
    for(int j=0; j<n; ++j) {
      M[i][j] = INFTY;
    }
  }

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

  for(int i=0; i<n; ++i) {
    int u, k;
    std::cin >> u >> k;
    for(int j=0; j<k; ++j) {
      int c, v;
      std::cin >> v >> c;
      M[u][v] = c;
    }
  }

  d[0] = 0;

  while(true) {
    int minicost = INFTY;
    int u;

    for(int i=0; i<n; ++i) {
      if(visited[i] == WHITE && d[i] < minicost) {
        minicost = d[i];
        u = i;
      }
    }

    if(minicost == INFTY) break;
    visited[u] = BLACK;

    for(int v=0; v<n; ++v) {
      if(d[u] + M[u][v] < d[v]) {
        d[v] = d[u] + M[u][v];
      }
    }
  }

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


}

C++: #include<iostream>
using namespace std;
static const int MAX = 100;
static const int INFTY = (1<<21);
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

struct Node{int color, dist, parent;};

int M[MAX][MAX], n;
Node node[MAX];

int main(){
  cin >> n;

  //initialize M and node
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      M[i][j] = INFTY;
    }
    node[i].color = WHITE;
    node[i].dist = INFTY;
    node[i].parent = -1;
  }

  //input distances
  for(int i = 0; i < n; i++){
    int u, k, v, c;
    cin >> u >> k;
    while(k--){
      cin >> v >> c;
      M[u][v] = c;
    }
  }

  int p = 0, min_dis;
  node[p].dist = 0;
  node[p].color = BLACK;

  while(true){
    for(int i = 0; i < n; i++){
      if(M[p][i] != INFTY && node[i].color != BLACK){
        int d = node[p].dist + M[p][i];
        if(node[i].dist > d){
          node[i].dist = d;
          node[i].color = GRAY;
          node[i].parent = p;
        }
      }
    }

    p = -1;
    min_dis = INFTY;
    for(int i = 0; i < n; i++){
      if(node[i].color == GRAY && node[i].dist < min_dis){
        p = i;
        min_dis = node[i].dist;
      }
    }

    if(p == -1)
      break;

    node[p].color = BLACK;
  }

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

C++: #include <iostream>
#include <vector>
#include <queue>
using namespace std;
	
const long long INF = 7+(1e+18);
typedef long long Weight;
struct Edge {  //src:辺の始点,dst:辺の終点,weight:辺の重さ
  int src, dst;
  Weight weight;
  Edge(int src, int dst, Weight weight) :
    src(src), dst(dst), weight(weight) { }
};
bool operator < (const Edge &e, const Edge &f) {
  return e.weight != f.weight ? e.weight > f.weight : //辺は重さが重いものを"小さい"と定義する
    e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

//引数 g:隣接リスト,s:始点,dist:各頂点までの距離が入る,prev:最短路木の親頂点が入る
//戻値 なし
void shortestPath(const Graph &g,int s,vector<Weight> &dist,vector<int> &prev) {
  int n = g.size();
  dist.assign(n, INF); dist[s] = 0;
  prev.assign(n, -1);
  priority_queue<Edge> Q;
  Q.push(Edge(-2, s, 0));
  while(!Q.empty()) {
    Edge e = Q.top(); Q.pop();
    if (prev[e.dst] != -1) continue;
    prev[e.dst] = e.src;
    for(auto f=g[e.dst].begin();f!=g[e.dst].end();f++){
      if (dist[f->dst] > e.weight+f->weight) {
        dist[f->dst] = e.weight+f->weight;
        Q.push(Edge(f->src, f->dst, e.weight+f->weight));
      }
    }
  }
}
//-----------------
int main()
{ 
    while(true){
        int i, j, k, V;
        int u, v;
        Weight c;
        if(!(cin >> V))break;
        Graph g(V);    //頂点数vの空隣接リストgを生成
        for(i=0; i<V; i++){
            cin >> u >> k;
            for(j=0; j<k; j++){
                cin >> v >> c;
                g[u].push_back(Edge(u, v, c));    //隣接リストgにsからtに向かう重さwの辺を追加
            }
        }
        vector<Weight> dist;
        vector<int> prev;
        shortestPath(g,0,dist,prev);
        for(i=0; i<V; i++){
            cout << i << " " << dist[i] << endl;
        }
    }
  
    return 0;
}

C++: #include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#define INF 100000000
#define ll long long
using namespace std;
int main(){
  int n;
  cin >> n;
  vector< vector< pair<int,int> > > edges(n);
  for(int i = 0; i < n; i++){
    int id = 0;
    cin >> id;
    int k;
    cin >> k;
    for(int j = 0; j < k; j++){
      int v, c;
      cin >> v >> c;
      edges[id].push_back(make_pair(v,c));
    }
  }

  priority_queue< pair<int,int>, vector< pair<int,int> > , less< pair<int,int> > > pq;
  pq.push(make_pair(0,0));
  vector<long long> dist(n, INF);
  dist[0] = 0;
  while(!pq.empty()){
    ll source = pq.top().second;
    pq.pop();
    for(pair<int,int> edge: edges[source]){
      if(dist[edge.first] > dist[source] + edge.second){
	dist[edge.first] = dist[source] + edge.second;
	pq.push(make_pair(dist[edge.first], edge.first));
      }
    }
  }
  for(int i = 0; i < n; i++){
    cout << i << ' ';
    cout << dist[i] << endl;
  }
}

C++: #include <map>
#include <vector>
#include <cstdio>
using namespace std;
int main(){
	int n=0,N,i,j,k,c;
	scanf("%d",&N);
	vector<map<int,int> >dist(N);
	vector<bool>used(N);
	vector<int>cost(N);
	for(;n<N;n++){
		cost[n]=9999999;
		for(scanf("%d%d",&i,&k);k--;dist[j][i]=c)scanf("%d%d",&j,&c); //i->j cost c
	}
	for(cost[0]=0;;){ //dijkstra
		int m=9999999;
		for(i=0;i<N;i++)if(!used[i]&&m>cost[i])m=cost[i];
		if(m==9999999)break;
		for(j=0;j<n;j++)if(m==cost[j]){
			map<int,int>::iterator it=dist[j].begin();
			for(used[j]=1;it!=dist[j].end();it++)if(cost[it->first]>it->second+cost[j])cost[it->first]=it->second+cost[j];
		}
	}
	for(i=0;i<n;i++)printf("%d %d\n",i,cost[i]);
}