Go: package main

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

const (
	MAX_N      = 10000
	MAX_WEIGHT = 100000
)

type Edge struct {
	start  int
	end    int
	weight int
}

type ShortestInfo struct {
	edges    []Edge
	shortest int
}

type Neighbor struct {
	node   int
	weight int
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	n, err := nextInt(sc)
	if err != nil {
		panic(err)
	}

	shortestList := make([]ShortestInfo, n)
	for i := 1; i < n; i++ {
		shortestList[i] = ShortestInfo{edges: []Edge{}, shortest: MAX_N*MAX_WEIGHT + 1}
	}

	adjacentMatrix, err := createAdjacentMatrix(n, sc)
	if err != nil {
		panic(err)
	}

	sssp([]int{0}, shortestList, adjacentMatrix)
	for _, v := range shortestList {
		fmt.Printf("%d %d\n", v.getEnd(), v.shortest)
	}
}

func (si ShortestInfo) getEnd() int {
	if len(si.edges) == 0 {
		return 0
	} else {
		return si.edges[len(si.edges)-1].end
	}
}

func createAdjacentMatrix(n int, sc *bufio.Scanner) ([][]Neighbor, error) {
	adjacentMatrix := make([][]Neighbor, n)
	for i := 0; i < n; i++ {
		id, err := nextInt(sc)
		if err != nil {
			return nil, err
		}
		adjacentMatrix[id] = []Neighbor{}
		vertexNum, err := nextInt(sc)
		if err != nil {
			return nil, err
		}
		for j := 0; j < vertexNum; j++ {
			v, err := nextInt(sc)
			if err != nil {
				return nil, err
			}
			c, err := nextInt(sc)
			if err != nil {
				return nil, err
			}
			adjacentMatrix[id] = append(adjacentMatrix[id], Neighbor{v, c})
		}
	}
	return adjacentMatrix, nil
}

func sssp(nodeStack []int, shortestList []ShortestInfo, adjacentMatrix [][]Neighbor) {
	for len(nodeStack) > 0 {
		currentNode := nodeStack[0]
		nodeStack = nodeStack[1:]
		currentShortest := getShortest(currentNode, shortestList)
		adjacents := findAdjacents(currentNode, adjacentMatrix)
		for i := 0; i < len(adjacents); i++ {
			adj := adjacents[i]
			if currentShortest.shortest+adj.weight < getShortest(adj.end, shortestList).shortest {
				setShortest(adj.end, adj, currentShortest, shortestList)
				nodeStack = append(nodeStack, adj.end)
			}
		}
	}
}

func getShortest(node int, shortestList []ShortestInfo) ShortestInfo {
	return shortestList[node]
}

func setShortest(node int, edge Edge, currentShortest ShortestInfo, shortestList []ShortestInfo) {
	newEdges := make([]Edge, len(currentShortest.edges)+1)
	for i := 0; i < len(newEdges)-1; i++ {
		newEdges[i] = currentShortest.edges[i]
	}
	newEdges[len(newEdges)-1] = edge
	shortestInfo := ShortestInfo{edges: newEdges, shortest: currentShortest.shortest + edge.weight}
	shortestList[node] = shortestInfo
}

func findAdjacents(currentNode int, adjacentMatrix [][]Neighbor) []Edge {
	adjacents := adjacentMatrix[currentNode]
	edges := []Edge{}
	for _, neighbor := range adjacents {
		edges = append(edges, Edge{start: currentNode, end: neighbor.node, weight: neighbor.weight})
	}
	return edges
}

func nextInt(sc *bufio.Scanner) (int, error) {
	sc.Scan()
	return strconv.Atoi(sc.Text())
}

C++: #include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <climits>
#define int long long
using namespace std;
typedef pair <int,int> P;
#define to first
#define co second
#define fi first
#define se second
const int INF=INT_MAX;
const int MAX_V=100000;
vector <P> G[MAX_V];
int v,d[MAX_V];
void dijk(int s){
  priority_queue <P,vector<P>,greater<P> > que;
  fill(d,d+v,INF);
  d[s]=0;
  que.push(P(0,s));
  for(;!que.empty();){
    P p=que.top(); que.pop();
    int v=p.se;
    if (d[v]<p.fi) continue;
    for(int i=0;i<(int)G[v].size();i++){
      P e=G[v][i];
      if(d[e.to]>d[v]+e.co){
	d[e.to]=d[v]+e.co;
	que.push(P(d[e.to],e.to));
      }
    }
  }
}
signed main(){

  cin>>v;
  for(int i=0,u,k;i<v&&cin>>u>>k;i++) for(int j=0,a,b;j<k&&cin>>a>>b;j++) G[u].push_back(P(a,b));
  dijk(0);
  for(int i=0;i<v;i++) cout<<i<<" "<<d[i]<<endl;
  return 0;

}

C++: #include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;

map <int,int> mp;

#define INF (1<<30)
#define INFLL (1ll<<60)
#define EPS (1e-10)
static const int MAX=1e5;
static const int MOD=1e9+7;
static const int NMAX=50;
static const int MMAX=50;
int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};

typedef pair<int, int> P; //最短距離,頂点の番号
struct edge{
    int to,cost;
};
int N;
vector<edge> G[MAX]; //
int d[MAX]; //最短距離

void dijkstra(int s){
    priority_queue<P, vector<P>,greater<P> > que;
    
    fill(d,d+N,INF);
    d[s]=0;
    que.push(P(0,s));
    
    while(!que.empty()){
        P p=que.top(); que.pop();
        int v=p.second;
        
        if(d[v] < p.first) continue;
        for(int i=0;i<G[v].size();i++){
            edge e=G[v][i];
            if(d[e.to]>d[v]+e.cost){
                d[e.to] =d[v]+e.cost;
                que.push(P(d[e.to],e.to));
            }
        }
    }
}


int main(){
    cin.tie(0);  ios::sync_with_stdio(false);
    
    int k,u;
    cin>>N;
    for(int i=0;i<N;i++){
        cin>>u>>k;
        for(int j=0;j<k;j++){
            edge e;
            cin>>e.to>>e.cost;
            G[u].push_back(e);
        }
    }
    dijkstra(0);
    for(int i=0;i<N;i++)
        cout<<i<<" "<<(d[i]==INF?-1:d[i])<<"\n";
    
    return 0;
    }

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
typedef pair<ll,P>  PP;
typedef vector<ll> Vector;
typedef vector<Vector> DVector;
typedef priority_queue<P, vector<P>, greater<P>> PQueue;

#define fi          first
#define se          second
#define sfi         se.fi
#define sse         se.se
#define pb          push_back
#define INF         INT_MAX
#define MOD         1000000007
#define bcnt        __builtin_popcount
#define all(x)      (x).begin(),(x).end()
#define uni(x)      x.erase(unique(all(x)),x.end())
#define ub(x,y)     (upper_bound(all(x),y)-x.begin())
#define lb(x,y)     (lower_bound(all(x),y)-x.begin())
#define rep(i,n)    repl(i,0,n-1)
#define usort(x)    sort(all(x))
#define dsort(x)    sort(all(x),greater<ll>())
#define mkp(x,y)    make_pair(x,y)
#define mmax(x,y)   (x>y?x:y)
#define mmin(x,y)   (x<y?x:y)
#define maxch(x,y)  x=mmax(x,y)
#define minch(x,y)  x=mmin(x,y)
#define exist(x,y)  (find(all(x),y)!=x.end())
#define each(itr,v) for(auto itr:v)
#define repl(i,a,b) for(ll i=(ll)(a);i<=(ll)(b);i++)
DVector costs;
ll n;
Vector mincost;
void djk(ll start){
  PQueue pq;
  mincost.resize(n,INF);
  pq.push({0,start});
  while(pq.size()){
    P state = pq.top();pq.pop();
    if(mincost[state.se] <= state.fi)continue;
    mincost[state.se] = state.fi;
    rep(i,n)pq.push({mmin(mincost[state.se]+costs[state.se][i],mincost[i]),i});
  }
}

int main(){
  cin.sync_with_stdio(false);
  cin >> n;
  costs.resize(n,Vector(n,INF));
  rep(i,n){
    ll u,k;
    cin >> u >> k;
    rep(j,k){
      ll v,c;
      cin >> v >> c;
      costs[u][v] = c;
    }
  }
  djk(0);
  rep(i,n)cout << i << " " << mincost[i] << endl;
}