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

	list := make([][]int, n)
	weight := make([]int, n)
	for i := range list {
		list[i] = make([]int, n)
		weight[i] = NIL
		for j := range list[i] {
			list[i][j] = NIL
		}
	}

	for i := 0; i < n; i++ {
		u := scanInt()
		k := scanInt()
		for j := 0; j < k; j++ {
			v := scanInt()
			w := scanInt()
			list[u][v] = w
		}
	}

	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 i, w := range list[node.id] {
			if w == NIL {
				continue
			}
			heap.Push(h, Node{id: i, weight: w + node.weight})
		}
	}

	w := bufio.NewWriter(os.Stdout)
	for i := 0; i < n; i++ {
		fmt.Fprint(w, i)
		fmt.Fprint(w, " ")
		fmt.Fprint(w, weight[i])
		fmt.Fprintln(w)
	}
	w.Flush()
}

C++: #include<cstdio>
#include<vector>
#include<algorithm>
#include<utility>
#include<numeric>
#include<iostream>
#include<array>
#include<string>
#include<sstream>
#include<stack>
#include<queue>
#include<list>
#include<functional>
#define _USE_MATH_DEFINES

#include<math.h>
#include<map>

#define SENTINEL 1000000001

#define min(a,b) (a)>(b)?(b):(a)
#define max(a,b) (a)>(b)?(a):(b)

using namespace std;

struct OwnNode
{
	vector<int> to;
	vector<int> to_cost;

	int id;
	bool checked;
	int cost;

	OwnNode(int id):id(id),checked(false),cost(-1){}

	bool operator<(const OwnNode& node)const
	{
		return cost < node.cost;
	}

	bool operator>(const OwnNode& node)const
	{
		return cost > node.cost;
	}

	OwnNode operator-(const OwnNode& node)const
	{
		return cost - node.cost;
	}
};

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

	vector<OwnNode> nodes;

	for (int i = 0; i < n; i++)
	{
		int id, k;
		cin >> id >> k;

		nodes.push_back(OwnNode(id));

		for (int j = 0; j < k; j++)
		{
			int v, c;
			cin >> v >> c;
			nodes[i].to.push_back(v);
			nodes[i].to_cost.push_back(c);
		}
	}

	priority_queue<OwnNode, vector<OwnNode>, greater<OwnNode>> pq;

	nodes[0].cost = 0;
	pq.push(nodes[0]);

	while (pq.size() != 0)
	{
		OwnNode tn = pq.top();
		pq.pop();

		nodes[tn.id].checked = true;

		for (int i = 0; i != tn.to.size(); i++)
		{
			if (nodes[tn.to[i]].checked)continue;
			if (nodes[tn.to[i]].cost == -1)
			{
				nodes[tn.to[i]].cost = tn.to_cost[i];
			}
			else
			{
				nodes[tn.to[i]].cost = min(nodes[tn.to[i]].cost, tn.to_cost[i] + tn.cost);
			}
			pq.push(nodes[tn.to[i]]);
		}
	}

	for (auto& node : nodes)
	{
		printf("%d %d\n", node.id, node.cost);
	}

	return 0;
}

C++: #include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

using Weight=int;
using DArray=vector<Weight>;
using DMatrix=vector<DArray>;

static const Weight INF=1<<29;

struct Edge {
    size_t src, dst;
    Weight weight;
    Edge() {}
    Edge(size_t src, size_t dst, Weight weight=1):
        src(src), dst(dst), weight(weight)
    {}
};

bool operator<(const Edge &e, const Edge &f) {
    if (e.weight != f.weight) {
        return e.weight > f.weight;
    } else {
        return e.src!=f.src? e.src<f.src : e.dst<f.dst;
    }
}

using Edges=vector<Edge>;
using Vertex=vector<Edge>;
using Graph=vector<Vertex>;

void join(Graph &g, size_t s, size_t d, Weight w=1) {
    // non-directed
    g[s].push_back(Edge(s, d, w));
    g[d].push_back(Edge(d, s, w));
}

void connect(Graph &g, size_t s, size_t d, Weight w=1) {
    // directed
    g[s].push_back(Edge(s, d, w));
}

template <class T>
using lp_queue=priority_queue<T, deque<T>, greater<T>>;

template <typename T, typename U=size_t>
union raw_cast {
    public:
        constexpr raw_cast(T t): _t(t) {}
        operator U() const {
            return _u;
        }

    private:
        T _t;
        U _u;
};

size_t bsr(size_t n) {
    /* Bit scan reverse */
    // logarithmus binarius
    if (!n) return -1;

    size_t res;
    for (res=0; n>>=1; ++res)
        if (!n) return res;

    return res;
}

template <class Index, class T, size_t bucketSize=sizeof(Index)<<3>
struct RadixHeap {
    vector<pair<Index, T>> v[bucketSize|1];
    Index last;
    size_t size_;
    RadixHeap(): last(0), size_(0) {}
    void push(Index n, T t) {
        if (last > n) return;

        ++size_;
        size_t idx=raw_cast<Index>(n);
        idx ^= raw_cast<Index>(last);
        v[bsr(idx)+1].push_back(make_pair(n, t));
    }
    void push(pair<Index, T> p) {
        push(p.first, p.second);
    }
    void pop() {
        if (!size_) return;
        if (!v[0].size()) {
            size_t i; for (i=1; !v[i].size(); ++i);
            last = min_element(v[i].begin(), v[i].end())->first;
            for (const pair<Index, T> &p: v[i]) {
                size_t idx=raw_cast<Index>(p.first);
                idx ^= raw_cast<Index>(last);
                v[bsr(idx)+1].push_back(p);
            }

            v[i].clear();
        }
        --size_;
        v[0].pop_back();
    }
    pair<Index, T> top() {
        if (!size_) return pair<Index, T>();
        if (!v[0].size()) {
            size_t i; for (i=1; !v[i].size(); ++i);
            last = min_element(v[i].begin(), v[i].end())->first;
            for (const pair<Index, T> &p: v[i]) {
                size_t idx=raw_cast<Index>(p.first);
                idx ^= raw_cast<Index>(last);
                v[bsr(idx)+1].push_back(p);
            }

            v[i].clear();
        }
        return v[0].back();
    }
    size_t size() {
        return size_;
    }
    bool empty() {
        return !size_;
    }
    void clear() {
        last = size_ = 0;
        for (size_t i=0; i<=bucketSize; ++i)
            v[i].clear();
    }
};

vector<Weight> shortest_distance(const Graph &g, size_t s) {
    /* Dijkstra */
    size_t V=g.size();
    vector<Weight> d(V, INF); d[s]=0;

    RadixHeap<Weight, size_t> q; q.push(0, s);
    while (!q.empty()) {
        pair<Weight, size_t> p=q.top(); q.pop();
        size_t v=p.second;
        if (d[v] < p.first) continue;

        for (const Edge &e: g[v])
            if (d[e.dst] > d[v] + e.weight) {
                d[e.dst] = d[v] + e.weight;
                q.push(d[e.dst], e.dst);
            }
    }
    return d;
}

int main() {
    size_t n;
    scanf("%zu", &n);

    Graph g(n);
    for (size_t i=0; i<n; ++i) {
        size_t u, k;
        scanf("%zu %zu", &u, &k);

        for (size_t j=0; j<k; ++j) {
            size_t c;
            Weight v;
            scanf("%zu %d", &c, &v);

            connect(g, u, c, v);
        }
    }

    vector<Weight> d=shortest_distance(g, 0);
    for (size_t i=0; i<n; ++i)
        printf("%zu %d\n", i, d[i]);

    return 0;
}