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<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<sstream>
#include<cmath>
#include<numeric>
#include<map>
#include<stack>
#include<queue>
using namespace std;
int inf = 1000000000;

class node{
public:
  int to;
  int from;
  int cost;
};

int main(void) {

  int n; scanf("%d", &n);
  vector< vector<node> > v(n);
  for(int i=0; i<n; i++){
    int u, k;
    scanf("%d %d", &u, &k);
    for(int j=0; j<k; j++){
      int vv, c;
      scanf("%d %d", &vv, &c);
      node t;
      t.from = u;
      t.to = vv;
      t.cost = c;
      v[u].push_back(t);
    }
  }

  vector<int> dist(n, inf);
  vector<bool> vis(n, false);

  priority_queue< pair<int, int> > pq;
  pq.push(make_pair(0, 0));
  dist[0] = 0;
  vis[0] = true;
  while( !pq.empty() ){
    pair<int, int> pos = pq.top();
    pq.pop();
    int p = pos.second;
    vis[p] = true;
    for(int i=0; i<v[p].size(); i++){
      if( vis[v[p][i].to] ) continue;
      int tmp = dist[v[p][i].from] + v[p][i].cost;
      if( dist[v[p][i].to] <= tmp ) continue;

      dist[v[p][i].to] = tmp;
      pq.push(make_pair(dist[v[p][i].to]*-1, v[p][i].to));

    }

  }

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

  return 0;
}

// EOF

C++: #include <cstdio>
#include <cctype>
#include <climits>
#include <vector>
#include <queue>
using namespace std;

#define si static inline
#define gcu getchar_unlocked
si int in() {
	int c, n = 0;
	bool minus = false;
	if ((c = gcu()) == '-') minus = true; else ungetc(c, stdin);
	while ((c = gcu()) >= '0' && c <= '9') n = 10 * n + (c - '0');
	//return n; }
	return minus ? -n : n; }
si void scan(char *s) {while (!isspace(*s++ = gcu()));}
#define pcu putchar_unlocked
#define svo si void out
template <typename T>
svo(T n) {
	static char buf[20];
	char *p = buf;
	//if(n < 0) pcu('-'), n *= -1;
	if (!n) *p++ = '0';
	else while (n) *p++ = n % 10 + '0', n /= 10;
	while (p != buf) pcu(*--p); }
svo(const char *s){while(*s)pcu(*s++);}
svo(char *s){while(*s)pcu(*s++);}
svo(char c){pcu(c);}
template <typename T>
//svo(vector<T> &v){for(T &x:v)out(' '),out(x);out('\n');}
svo(vector<T> &v){for(T &x:v)out(&x == &v[0]?"":" "),out(x);out('\n');}
template <typename head, typename... tail>
svo(head&& h, tail&&... t){out(h);out(move(t)...);}
#undef svo
#undef si

#define v vector
struct graph {
	struct node {int n, w;};
	v<v<node>> nodes;

	void read(int n) {
		nodes.resize(n);
		for (auto &x: nodes) {
			in();
			for (int k = in(); k--;) {
				int c = in();
				x.push_back({c, in()});
			}
		}
	}

	v<node> dks() {
		v<node> w(nodes.size(), {0, INT_MAX});
		w[0].w = 0;
		priority_queue<node> q;
		q.push({0, 0});
		while (!q.empty()) {
			node n = q.top();
			q.pop();
			for (node &x: nodes[n.n]) {
				w[x.n].w = min(w[x.n].w, n.w + x.w);
				if (!w[n.n].n)
					q.push({x.n, w[x.n].w});
			}
			w[n.n].n = 1;
		}
		return move(w);
	}
};

bool operator < (const graph::node &a, const graph::node &b) {
	return a.w > b.w;
}

int main() {
	graph g;
	g.read(in());
	int i = 0;
	for (auto &x: g.dks())
		out(i++, ' ', x.w, '\n');
}

C++: #include<iostream>
#include<vector>
#include<climits>
#include<cmath>
#include<queue>

using namespace std;

struct edge {
  int to, cost;
};

struct state {
  int pos, cost;

  bool operator < (const state& s) const {
    return cost > s.cost;
  }
};

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

  vector< vector<edge> > edges(n, vector<edge>());
  for (int i = 0; i < n; i++) {
    int u, k; cin >> u >> k;

    while (k--) {
      int to, cost; cin >> to >> cost;
      edges[u].push_back((edge) { to, cost});
    }
  }

  priority_queue<state> queue;
  vector<int> costs(n, INT_MAX);
  costs[0] = 0;
  queue.push((state) {0, 0});

  while(!queue.empty()) {
    const state now = queue.top();
    queue.pop();

    if (costs[now.pos] < now.cost) continue;
    
    for (int i = 0; i < edges[now.pos].size(); i++) {
      state nex = now;
      nex.pos = edges[now.pos][i].to;
      nex.cost += edges[now.pos][i].cost;
      if (costs[nex.pos] > nex.cost) {
        costs[nex.pos] = nex.cost;
        queue.push(nex);
      }
    }
  }

  for (int i = 0; i < n; i++)
    cout << i << " " << costs[i] << endl;
  
  return 0;
}