Go: package main

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

const (
	white int = iota
	gray
	black
)

type node struct {
	id     int
	parent int
	edge   []int
	weight []int
	color  int
}

type graph struct {
	nodes    []node
	distance []int
}

var infty = 1 << 32
var null = -1

func constructgraph() *graph {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	n := nextInt(sc)

	g := &graph{make([]node, n), make([]int, n)}

	for i := 0; i < n; i++ {
		id := nextInt(sc)
		edges := nextInt(sc)
		n := node{}
		n.id = id
		n.edge = make([]int, edges)
		n.weight = make([]int, edges)
		n.color = white
		for j := 0; j < edges; j++ {
			to := nextInt(sc)
			w := nextInt(sc)
			n.edge[j] = to
			n.weight[j] = w
		}
		g.nodes[id] = n
	}
	return g
}

func nextInt(sc *bufio.Scanner) int {
	sc.Scan()
	v, _ := strconv.Atoi(sc.Text())
	return v
}

func (g *graph) preparedijkstra(s int) {
	for i := 0; i < len(g.nodes); i++ {
		g.nodes[i].color = white
		g.nodes[i].parent = null
		g.distance[i] = infty
	}
	g.distance[s] = 0
}

func (g *graph) dijkstra(s int) []int {
	g.preparedijkstra(s)

	for {
		var u int
		mincost := infty
		for i, d := range g.distance {
			if g.nodes[i].color != black && mincost > d {
				mincost = d
				u = i
			}
		}

		if mincost == infty {
			break
		}

		g.nodes[u].color = black

		for i, e := range g.nodes[u].edge {
			if g.nodes[e].color != black {
				if g.distance[e] > g.distance[u]+g.nodes[u].weight[i] {
					g.distance[e] = g.distance[u] + g.nodes[u].weight[i]
					g.nodes[e].parent = u
					g.nodes[e].color = gray
				}
			}
		}
	}
	return g.distance
}

func printShortestPath(d []int) {
	for i, v := range d {
		fmt.Printf("%d %d\n", i, v)
	}
}

func main() {
	g := constructgraph()
	d := g.dijkstra(0)
	printShortestPath(d)
}

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;
}