Go: package main

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

var scanner = bufio.NewScanner(os.Stdin)

func nextString() string {
	scanner.Scan()
	return scanner.Text()
}

func nextInt() int {
	n, err := strconv.Atoi(nextString())
	if err != nil {
		fmt.Printf("strconv.Atoi failed: %v\n", err)
	}
	return n
}

var infty = 1000000000

type DirectedGraphNodeID int

type DirectedGraphNode struct {
	key         DirectedGraphNodeID
	adjacents   []*DirectedGraphNode
	costs       []int
	distance    int
	predecessor *DirectedGraphNode
}

func newDirectedGraph(nNodes int) *DirectedGraph {
	graph := DirectedGraph{}
	graph.nodes = make([]*DirectedGraphNode, nNodes)
	for i := 0; i < nNodes; i++ {
		node := DirectedGraphNode{}
		node.key = DirectedGraphNodeID(i)
		node.distance = infty
		graph.nodes[i] = &node
	}
	return &graph
}

type DirectedGraph struct {
	nodes []*DirectedGraphNode
}

func (g *DirectedGraph) setAdjacency(i, j DirectedGraphNodeID, cost int) {
	g.nodes[i].adjacents = append(g.nodes[i].adjacents, g.nodes[j])
	g.nodes[i].costs = append(g.nodes[i].costs, cost)
}

func (g *DirectedGraph) print() {
	for i := 0; i < len(g.nodes); i++ {
		node := g.nodes[i]
		key := node.key
		strings := []string{strconv.Itoa(int(key)), strconv.Itoa(node.distance)}
		for j := 0; j < len(node.adjacents); j++ {
			nodeJ := fmt.Sprintf("(%v, %v)", node.adjacents[j].key, node.costs[j])
			strings = append(strings, nodeJ)
		}
		fmt.Printf("%v\n", strings)
	}
}

func (g *DirectedGraph) relaxEdge(l, r *DirectedGraphNode, w int) {
	if r.distance > l.distance+w {
		// fmt.Printf("%v -> %v, %v\n", l.key, r.key, l.distance+w)
		r.distance = l.distance + w
		r.predecessor = l
	}
}

func main() {
	scanner.Split(bufio.ScanWords)

	nNodes := nextInt()
	graph := newDirectedGraph(nNodes)

	for i := 0; i < nNodes; i++ {
		iNode := DirectedGraphNodeID(nextInt())
		nAdjacent := nextInt()
		for j := 0; j < nAdjacent; j++ {
			jNode := DirectedGraphNodeID(nextInt())
			cost := nextInt()
			graph.setAdjacency(iNode, jNode, cost)
		}
	}

	graph.nodes[0].distance = 0
	for iNode := 0; iNode < nNodes; iNode++ {
		for iLeft := 0; iLeft < len(graph.nodes); iLeft++ {
			nodeLeft := graph.nodes[iLeft]
			for iRight := 0; iRight < len(nodeLeft.adjacents); iRight++ {
				nodeRight := nodeLeft.adjacents[iRight]
				cost := nodeLeft.costs[iRight]
				graph.relaxEdge(nodeLeft, nodeRight, cost)
			}
		}
	}

	// graph.print()

	for iNode := 0; iNode < len(graph.nodes); iNode++ {
		node := graph.nodes[iNode]
		fmt.Println(node.key, node.distance)
	}
}

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 GRRAY = 1;
static const int BLACK = 2;

int n;
int M[100][100];

int dijkstra(){
  int u,minv,i,v;
  int d[MAX],color[MAX];

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

  d[0]=0;
  color[0]=GRRAY;
  while(1){
    minv=INFTY;
    u=-1;
    for(i=0;i<n;i++){
      if(minv>d[i] && color[i] != BLACK){
	u=i;
	minv=d[i];
      }
    }
    if(u==-1) break;
    color[u]=BLACK;
    for(v=0;v<n;v++){
      if(M[u][v] != INFTY && color[v] != BLACK){
	if(d[v]>d[u]+M[u][v]){
	  d[v]=d[u]+M[u][v];
	  color[v]=GRRAY;
	}
      }
    }
  }
    for(i=0;i<n;i++){
      cout << i << " " << (d[i] == INFTY ? -1 : d[i]) << endl;
    }
}

int main(){
  int i,j;

  cin >> n;
 
 for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      M[i][j]=INFTY;
    }
  }

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

C++: #include <iostream>
#include<cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
ll dp[105][105];
const ll INF = 0x3f3f3f3f;
int main()
{
    int n,i,m,j,a,b,k;
    scanf("%d",&n);
    for(i = 0;i < n;i++)
        for(j = 0;j < n;j++)
            dp[i][j] = INF;
    dp[0][0] = 0;
    for(j = 0;j < n;j++)
    {
        cin >> i >> m;
        while(m--)
        {
            cin >> a ;
            cin >> dp[i][a];
        }
    }
    for(k = 0;k < n;k++)
        for(i = 0;i < n;i++)
            for(j = 0;j < n;j++)
                dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j]);
    for(i = 0;i < n;i++)
        cout << i << ' ' << dp[0][i] << endl;
    return 0;
}

C++: #include<bits/stdc++.h>
#define ll long long
#define rep(i, n) for(int i=0;i<(n);++i)
#define per(i, n) for(int i=(n)-1;i>=0;--i)
#define repa(i, n) for(int i=1;i<(n);++i)
#define foreach(i, n) for(auto &i:(n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define all(x) (x).begin(), (x).end()
#define bit(x) (1ll << (x))
const ll MOD = (ll)1e9+7;
const int INF = (ll)1e9+7;
const ll INFLL = (ll)1e18;
using namespace std;
template<class t>
using vvector = vector<vector<t>>;
template<class t>
using vvvector = vector<vector<vector<t>>>;
template<class t>
using priority_queuer = priority_queue<t, vector<t>, greater<t>>;
template<class t, class u> bool chmax(t &a, u b){if(a<b){a=b;return true;}return false;}
template<class t, class u> bool chmin(t &a, u b){if(a>b){a=b;return true;}return false;}

ll modpow(ll x, ll b){
	ll res = 1;
	while(b){
		if(b&1)res = res * x % MOD;
		x = x * x % MOD;
		b>>=1;
	}
	return res;
}

ll modinv(ll x){
	return modpow(x, MOD-2);
}

bool was_output = false;
template<class t>
void output(t a){
	if(was_output)cout << " ";
	cout << a;
	was_output = true;
}
void outendl(){
	was_output = false;
	cout << endl;
}

class dijkstra{
public:
	int n;
	vvector<pll> edges;
	vector<ll> fast;
	dijkstra(int N):n(N){
		edges.resize(n);
	}

	void add_edge(int from, int to, ll cost){
		edges[from].emplace_back(to, cost);
	}

	void solve(int start){
		priority_queuer<pll> pq;
		fast.assign(n, INFLL);
		pq.emplace(0, 0);
		fast[start] = 0;
		pq.emplace(0, start);
		while(pq.size()){
			pll d = pq.top();
			pq.pop();
			if(d.first!=fast[d.second])continue;
			foreach(i, edges[d.second]){
				ll next_time = d.first + i.second;
				int to = i.first;
				if(fast[to] <= next_time)continue;
				fast[to] = next_time;
				pq.emplace(next_time, to);
			}
		}
	}
};


int main(){
	int n;
	cin >> n;
	dijkstra dij(n);
	rep(i, n){
		int from;
		cin >> from;
		int time;
		cin >> time;
		rep(j, time){
			int to;
			ll cost;
			cin >> to >> cost;
			dij.add_edge(from, to, cost);
		}
	}
	dij.solve(0);
	rep(i, n){
		output(i);
		output(dij.fast[i]);
		outendl();
	}
	return 0;
}

C++: #include <iostream>
using namespace std;

#define N 100
#define INFTY (1<<21)
#define WHITE 0
#define GRAY 1
#define BLACK 2

int n, M[N][N];
int color[N], d[N], p[N];

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

  while(true){
    mincost = INFTY;
    int u = -1;
    for(int i = 0 ; i < n; i++){
      if(color[i] != BLACK && d[i] < mincost){
        mincost = d[i];
        u = i;
      }
    }
    if(mincost == INFTY){
      break;
    }
    color[u] = BLACK;

    for(int v = 0 ; v < n ; v++ ){
      if(color[v] != BLACK && M[u][v] != INFTY){
        if(d[u] + M[u][v] < d[v]){
          d[v] = d[u] + M[u][v];
          p[v] = u;
          color[v] = GRAY;
        }
      }
    }
  }
}

int main(){
  cin >> n;
  for(int i = 0 ; i < n ; i++){
    for(int j = 0 ; j < n ; j++){
      M[i][j] = INFTY;
    }
    int u, k;
    cin >> u >> k;
    for(int j = 0 ; j < k ; j++){
      int v , c;
      cin >> v >> c;
      M[u][v] = c;
    }
  }
  dijkstra(0);
  /*for(int i = 0; i < n ; i++){
    for(int j = 0 ; j < n ; j++){
      cout << M[i][j] << " " ;
    }
    cout << "\n";
  }*/
  for(int i = 0 ; i < n ; i++){
    cout << i << " " << d[i] << "\n";
  }
  return 0;
}