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()

	route := make([][]Node, n)
	weight := make([]int, n)
	for i := 0; i < n; i++ {
		weight[i] = NIL
	}

	for i := 0; i < n; i++ {
		u := scanInt()
		k := scanInt()
		route[i] = make([]Node, k)
		for j := 0; j < k; j++ {
			route[u][j] = Node{id: scanInt(), weight: scanInt()}
		}
	}

	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 _, nextNode := range route[node.id] {
			if weight[nextNode.id] != NIL {
				continue
			}
			nextNode.weight += node.weight
			heap.Push(h, nextNode)
		}
	}

	for i, w := range weight {
		fmt.Println(i, w)
	}
}

C++: #include <bits/stdc++.h>
using namespace std;
struct Graph{
  using seen_t=size_t; using ver_t=size_t; using edge_t=pair<ver_t,seen_t>;
  const seen_t NO=1e9;
  vector<seen_t> seen;
  vector<vector<edge_t>> edge;
  Graph(size_t n): seen(n,NO), edge(n) {}

  void search(ver_t v0){
    seen[v0]=0;
    priority_queue<pair<seen_t,ver_t>,vector<pair<seen_t,ver_t>>,greater<pair<seen_t,ver_t>>> que; que.push(make_pair(0,v0)); // dijkstra
    ver_t curv; seen_t alt;
    while(!que.empty()){
      curv=que.top().second; que.pop(); // dijkstra
      for(const auto& nextv:edge[curv]){
        alt=seen[curv]+nextv.second;
        if(seen[nextv.first]>alt && alt<NO){
          seen[nextv.first]=alt;
          que.push(make_pair(alt,nextv.first)); // dijkstra
        }
      }
    }
  }
};
ostream& operator<<(ostream& os, const Graph& x){
  for(size_t i=0; i<x.edge.size(); ++i){
    cout<<(i)<<' '<<x.seen[i]<<'\n';
  }
  return os;
}
int32_t main(){
  ios::sync_with_stdio(false); cin.tie(0);
  size_t n; cin>>n;
  Graph graph(n);
  size_t u,k,v,c;
  for(size_t i=0; i<n; ++i){
    cin>>u>>k;
    graph.edge[u].resize(k);
    for(size_t j=0; j<k; ++j){
      cin>>v>>c; graph.edge[u][j]=make_pair(v,c);
    }
  }
  graph.search(0);
  cout<<graph;
}

C++: #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <string>
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>

using namespace std;

// ---------------------
// repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

// debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

// ---------------------
#define INF (1 << 21)
typedef long long ll;

int main() {
  int n;
  cin >> n;

  vector<int> V[n];
  // int E[n][n];
  map<pair<int, int>, int> E;
  int d[n];
  int visited[n];

  priority_queue<pair<int, int> , vector<pair<int, int> >, greater<pair<int, int> > > Q;

  REP(i, n) {
    d[i] = INF;
    visited[i] = 0;
  }

  REP(_, n) {
    int u, k;
    cin >> u >> k;
    REP(__, k) {
      int v, c;
      cin >> v >> c;
      V[u].push_back(v);
      E[make_pair(u, v)] = c;
    }
  }

  d[0] = 0;
  Q.push(make_pair(d[0], 0));
  REP(_, n) {
    // int minv = -1;
    // int mincost = INF;
    // REP(v, n) {
    //   if (!visited[v] && d[v] < mincost) {
    //     minv = v;
    //     mincost = d[v];
    //   }
    // }
    int mincost = Q.top().first;
    int minv = Q.top().second;

    visited[minv] = 1;
    for (vector<int>::iterator it = V[minv].begin(); it != V[minv].end(); it++) {
      if (E[make_pair(minv, *it)] < INF && d[minv] + E[make_pair(minv, *it)] < d[*it]) {
        d[*it] = d[minv] + E[make_pair(minv, *it)];
        Q.push(make_pair(d[*it], *it));
      }
    }
  }

  REP(i, n) {
    cout << i << " " << d[i] << endl;
  }
  return 0;
}

C++: #include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
typedef long long int ll;

#define BIG_NUM 2000000000

using namespace std;

struct Node{

	Node(int arg_to,int arg_cost){
		to = arg_to;
		cost = arg_cost;
	}
	bool operator<(const struct Node &arg) const{
			return cost > arg.cost;
	};

	int to,cost;
};

int main(){

	int N;
	scanf("%d",&N);

	vector<Node> V[N];

	int node,num,to,cost,D[N];;

	for(int loop = 0; loop < N; loop++){
		scanf("%d",&node);
		scanf("%d",&num);
		for(int i = 0; i < num; i++){
			scanf("%d %d",&to,&cost);
			V[node].push_back(Node(to,cost));
		}
		D[loop] = BIG_NUM;
	}

	D[0] = 0;

	priority_queue<Node> Q;

	for(int i = 0; i < V[0].size(); i++){
		D[V[0][i].to] = V[0][i].cost;
		Q.push(Node(V[0][i].to,V[0][i].cost));
	}

	int min_index;

	while(!Q.empty()){
		if(Q.top().cost == D[Q.top().to]){
			min_index = Q.top().to;
			Q.pop();
		}else{
			Q.pop();
			continue;
		}

		for(int k = 0; k < V[min_index].size(); k++){
			if(D[V[min_index][k].to] > D[min_index] + V[min_index][k].cost){
				D[V[min_index][k].to] = D[min_index] + V[min_index][k].cost;
				Q.push(Node(V[min_index][k].to,D[V[min_index][k].to]));
			}
		}
	}

	for(int i = 0; i < N; i++)printf("%d %d\n",i,D[i]);

    return 0;
}

C++: #include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
 
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define repi(i,a,b) for(int i = (a); i < (b); i++)
 
using namespace std;
 
typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;
 
const int INF=1<<29;
const double EPS=1e-9;
 
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};
const int MAX_N =10000;
 
struct edge
{
    int to,cost;
    edge(int _to,int _cost){
        to =_to;
        cost =_cost;
    }
};
 
int V;
vector<edge> cost[MAX_N];
int d[MAX_N];
bool visit[MAX_N];
void dijkstra(int s){
    d[s]=0;
    priority_queue<pii, vector<pii> ,greater<pii> > que;
    que.push(mp(0,s));
    while(!que.empty()){
        pii p =que.top();
        que.pop();
        int v =p.second;
        //if(d[v] < p.first)continue;
        for(int i =0;i <cost[v].size();i++){
            edge e =cost[v][i];
            if(d[e.to] >d[v]+e.cost){
                d[e.to] =d[v] +e.cost;
                que.push(mp(d[e.to],e.to));
            }
        }
    }
}
 
int main(){
    cin>>V;
    for(int i =0;i <V;i++){
        d[i]=INF;
        int u,k;
        cin>>u>>k;
        for(int j =0;j <k;j++){
            int to,c;
            cin>>to>>c;
            cost[u].push_back(edge(to,c));
        }
    }
     
    dijkstra(0);
    for(int i =0;i <V;i++){
        cout <<i<<" "<<d[i]<<endl;
    }
    return 0;
}