Go: package main

import (
	"strconv"
	"fmt"
	"bufio"
	"os"
)
const INF = 1 << 21
var scanner = bufio.NewScanner(os.Stdin)

func nextInt() int {
	scanner.Scan()
	i, e := strconv.Atoi(scanner.Text())
	if e != nil {
		panic(e)
	}
	return i
}


func main() {
	scanner.Split(bufio.ScanWords)
	n := nextInt()
	adj := make([][]int, n)
	for i := range adj {
		adj[i] = make([]int, n)
	}

	for i := 0;i < n; i++ {
		u := nextInt()
		k := nextInt()
		for j := 0; j < k; j++ {
			v := nextInt()
			c := nextInt()
			adj[u][v] = c
		}
	}

	// for i := range adj {
	// 	fmt.Println(adj[i])
	// }

	dist := make([]int, n)
	prev := make([]int, n)
	visited := make([]bool, n)
	dijkstra := func(start int, size int) {
		for i := 0; i < size; i++ {
			dist[i] = INF
			prev[i] = -1
			visited[i] = false
		}
		dist[start] = 0
		for {
			u := -1
			tmp_min := INF
			for i := 0; i < size; i++ {
				if visited[i] == false && dist[i] < tmp_min {
					tmp_min = dist[i]
					u = i
				}
			}
			if u == -1 {
				break
			}
			visited[u] = true
			for i := 0; i < size; i++ {
				if adj[u][i] > 0 {
					w := adj[u][i]
					newlen := dist[u] + w
					if newlen < dist[i] {
						dist[i] = newlen
						prev[i] = u
					}
				}
			}
		}
	}
	dijkstra(0, n)
	for i, cost := range dist {
		fmt.Printf("%d %d\n", i, cost)
	}
}

C++: #include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   for(int i=0;i<(n);++i)
#define SORT(c)    sort((c).begin(),(c).end())
#define CLR(a)     memset((&a), 0 ,sizeof(a))//clear memory
#define dump(x)    cerr << #x << " = " << (x) << endl;//debug
#define debug(x)   cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define EPS        1e-10//sample:if((double)>=(double)+EPS)
//cin,cout release
//std::cin.tie(0);
//ios::sync_with_stdio(false);

using namespace std;
int n;
int d[100000];
int color[100000];
vector<pair<int,int> > adj[100000];
#define WHITE 0
#define BLACK 2
#define GRAY 1
void dijkstra(){
  rep(i,n)d[i]=INT_MAX;
  priority_queue< pair<int,int> > PQ;
  rep(i,n)color[i]=WHITE;
  d[0]=0;
  PQ.push(make_pair(0,0));
  color[0]=GRAY;
  while(!PQ.empty()){
    pair<int,int> f=PQ.top();
    PQ.pop();
    int u=f.second;
    color[u]=BLACK;
    if(d[u]<f.first*(-1))continue;
    rep(j,(int)adj[u].size()){
      int v=adj[u][j].first;
      if(color[v]==BLACK)continue;
      if(d[v]>d[u]+adj[u][j].second){
	d[v]=d[u]+adj[u][j].second;
	PQ.push(make_pair(d[v]*(-1),v));
	color[v]=GRAY;
      }
    }
  }
  rep(i,n)cout<<i<<" "<<(d[i]==INT_MAX?-1:d[i])<<endl;
}


int main(){
  int a,b,c,d;
  cin>>n;
  rep(i,n){
    cin>>a>>b;
    rep(j,b){
      cin>>c>>d;
      adj[a].push_back(make_pair(c,d));
    }
  }
  dijkstra();
  return 0;
}

C++: #include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int INF=1145141919,MOD=1e9+7;
const long long LINF=8931145141919364364,LMOD=998244353;
// const int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,-1,0,1,1,-1,-1,1};

const int VMAX=100010;
int V,E,start,goal;
vector<pair<long long,int>> edge[VMAX];
long long dist[VMAX];
bool used[VMAX];

void dijkstra(){
    // 距離をLINFで初期化
    rep(to,VMAX) dist[to]=LINF;
    // 始点は0
    dist[start]=0;
    // フラグを下げる
    rep(v,VMAX) used[v]=false;
    // 優先度付きキュー:[距離,頂点]←距離の昇順
    priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>> q;
    // 距離0,始点
    q.push({0,start});
    // dijkstra
    while(q.size()){
        // 取り出してd=距離,v=頂点
        pair<long long,int> p=q.top(); q.pop();
        long long d=p.first;
        int from=p.second;
        if(used[from]) continue;
        used[from]=true;
        // 頂点から出る辺すべてについて
        for(auto e:edge[from]){
            long long cost=e.first,to=e.second;
            // 短縮できるとき
            if(d+cost<dist[to]){
                dist[to]=d+cost;
                q.push({dist[to],to});
            }
        }
    }
}

int main(){
    cin>>V;
    rep(i,V){
        int u,k; cin>>u>>k;
        rep(j,k){
            int to,distance;
            cin>>to>>distance;
            edge[u].push_back({distance,to});
        }
    }
    start=0;
    dijkstra();
    rep(i,V){
        cout<<i<<" "<<dist[i]<<endl;
    }
    return 0;
}