Go: package main

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

// I/O
type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextFloat() float64 {
	f, e := strconv.ParseFloat(s.nextStr(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *Scanner) nextRuneSlice() []rune {
	return []rune(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func (s *Scanner) nextFloatSlice(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextFloat()
	}
	return res
}

// Arithmetic
func max(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m < i {
			m = i
		}
	}
	return m
}

func min(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m > i {
			m = i
		}
	}
	return m
}

func abs(x int) int {
	if x > 0 {
		return x
	}
	return -x
}

func pow(x, y int) int {
	res := 1
	for i := 0; i < y; i++ {
		res *= x
	}
	return res
}

func ceil(a, b int) int {
	if a%b == 0 {
		return a / b
	} else {
		return a/b + 1
	}
}

// Sort
type RuneSlice []rune

func (a RuneSlice) Len() int           { return len(a) }
func (a RuneSlice) Less(i, j int) bool { return a[i] < a[j] }
func (a RuneSlice) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

// Main
type Node struct {
	cost int
	done bool
}

type Edge struct {
	to, cost int
}

const INF = 1 << 60

func main() {
	sc := NewScanner()
	wtr := bufio.NewWriter(os.Stdout)
	N := sc.nextInt()
	nodes := make([]Node, N)
	for i := 0; i < N; i++ {
		nodes[i].cost = INF
	}
	E := make([][]Edge, N)
	for i := 0; i < N; i++ {
		id, k := sc.nextInt(), sc.nextInt()
		for j := 0; j < k; j++ {
			to, cost := sc.nextInt(), sc.nextInt()
			E[id] = append(E[id], Edge{to, cost})
		}
	}
	nodes[0].cost = 0
	for {
		cur := 0
		minCost := INF
		for i := 0; i < N; i++ {
			n := nodes[i]
			if !n.done && n.cost < minCost {
				cur = i
				minCost = n.cost
			}
		}
		if minCost == INF {
			break
		}
		nodes[cur].done = true
		for i := 0; i < len(E[cur]); i++ {
			to, cost := E[cur][i].to, E[cur][i].cost+nodes[cur].cost
			if !nodes[to].done && cost < nodes[to].cost {
				nodes[to].cost = cost
			}
		}
	}

	for i := 0; i < N; i++ {
		fmt.Fprintln(wtr, i, nodes[i].cost)
	}
	wtr.Flush()
}

C++: #include <cstdio>
#include <cstdint>
#include <iostream>
#include <fstream>
#include <cassert>
#include <climits>
#include <cinttypes>

#include <memory>
#include <queue>
#include <map>
#include <unordered_map>
using namespace std;

#define NDEBUG
#define MYDEBUG (0)

#if MYDEBUG
#define DPRINTF(...) do { \
    printf("D(L%d) %s: ", __LINE__, __func__); \
    printf(__VA_ARGS__); \
  } while (false)
#else
#define DPRINTF(...)
#endif // MYDEBUG


const int kMaxVertex = 10 * 1000;
const int kMaxWeight = 100 * 1000;
const int kMaxNumPath = 500 * 1000;
const int kInvalidWeight = -1;

int g_num_of_vertex;
int g_min_weight[kMaxVertex];


/*
   2D data structure ([x][y] = value)
*/
struct DstAndWeight {
    int dst_;
    int weight_;
};

struct StartIdxAndLen {
    int start_;
    int len_;
};

class WeightGraph {
public:
    WeightGraph()
    {
        end_weights_ = 0;
        end_idx_len_ = 0;

        const int n = kMaxNumPath;
        weights_ = unique_ptr<DstAndWeight[]>(new DstAndWeight[n]);

        DPRINTF("allocated weights_ ptr (%lu bytes)\n", sizeof(weights_));

        const int n2 = kMaxVertex;
        idx_len_ = unique_ptr<StartIdxAndLen[]>(new StartIdxAndLen[n2]);

        for (int i = 0; i < n2; i++)
        {
            idx_len_[i].start_ = -1;
            idx_len_[i].len_ = -1;
        }

        DPRINTF("allocated idx_len_ ptr (%lu bytes)\n", sizeof(idx_len_));
    }

    void setWeight(int from, const vector<int> &tos, const vector<int> &weights);
    int getWeight(int from, int to) const;
    vector<int> getConnectedVertices(int from) const;

private:
    inline int getLen(int v) const { return idx_len_[v].len_; }
    inline int getStartIdx(int v) const { return idx_len_[v].start_; }

    unique_ptr<DstAndWeight[]> weights_;
    unique_ptr<StartIdxAndLen[]> idx_len_;

    uint32_t end_weights_;
    uint32_t end_idx_len_;
};


void WeightGraph::setWeight(int from, const vector<int> &tos, const vector<int> &weights)
{
    assert(0 <= from && from < kMaxNumPath);
    assert(tos.size() == weights.size());
    assert(end_weights_ + tos.size() < kMaxNumPath);

    idx_len_[from].start_ = end_weights_;
    idx_len_[from].len_ = tos.size();

    for (int i = 0; i < tos.size(); i++)
    {
        weights_[end_weights_].dst_ = tos[i];
        weights_[end_weights_].weight_ = weights[i];
        end_weights_++;
    }

    end_idx_len_++;

}


int WeightGraph::getWeight(int from, int to) const
{
    const int start = getStartIdx(from);
    const int len = getLen(from);

    assert(0 <= start);
    assert(start + len <= end_weights_);

    for (int i = start; i < start + len; i++)
    {
        if (weights_[i].dst_ == to)
            return weights_[i].weight_;
    }

    return kInvalidWeight;
}

///////////////////////////////////////////////////
struct Edge {
    Edge(int num_vertex)
        : num_vertex_(num_vertex)
    {
        graph_ = new WeightGraph();
    }

    ~Edge()
    {
        delete graph_;
    }

    bool isConnected(int from, int to) const;
    vector<int> getConnectedVertices(int v) const;
    int getWeight(int from, int to) const;
    void setWeight(int from, const vector<int> &tos, const vector<int> &weights);
    void printWeight() const;

    int num_vertex_;

    WeightGraph *graph_;
};

bool Edge::isConnected(int from, int to) const
{
    if (from == to)
        return false;

    if (getWeight(from, to) == kInvalidWeight)
        return false;

    return true;
}

vector<int> Edge::getConnectedVertices(int v) const
{
    vector<int> vertices;

    for (int i = 0; i < num_vertex_; i++)
        if (isConnected(v, i))
            vertices.push_back(i);

    return vertices;
}

void Edge::setWeight(int from, const vector<int> &tos, const vector<int> &weights)
{
    assert(0 <= from && from < num_vertex_);
    for (const int t : tos)       assert(0 <= t && t < kMaxVertex && t < num_vertex_);
    for (const int w : weights)   assert(0 <= w && w < kMaxWeight);

    graph_->setWeight(from, tos, weights);
}

int Edge::getWeight(int from, int to) const
{
    return graph_->getWeight(from, to);
}

void Edge::printWeight() const
{
    for (int i = 0; i < num_vertex_; i++)
    {
        DPRINTF("%d:", i);

        for (int j = 0; j < num_vertex_; j++)
        {
            const int w = graph_->getWeight(i, j);
            if (w != kInvalidWeight)        printf(" %d", w);
            else                            printf(" -");
        }
        cout << endl;

    }
}


//////////////////////////////////////////////////////////////
struct VtxAndWeight {
    VtxAndWeight(int vtx, int weight)
        : vtx_(vtx)
        , weight_(weight)
    {}

    int vtx_;
    int weight_;

    bool operator>(const VtxAndWeight& rhs)
    {
        return (*this).weight_ > rhs.weight_;
    };

    bool operator<(const VtxAndWeight& rhs)
    {
        return (*this).weight_ < rhs.weight_;
    };
};

struct LessThanByWeight
{
    bool operator()(const VtxAndWeight& lhs, const VtxAndWeight& rhs) const
    {
        return lhs.weight_ > rhs.weight_;
    }

};


/* Dijkstra's algorithm */
void calcShortestPath(int start, const Edge &edge)
{
    priority_queue<VtxAndWeight, vector<VtxAndWeight>, LessThanByWeight> priority_queue;

    const int init_weight = 0;
    g_min_weight[start] = 0;
    priority_queue.push(VtxAndWeight(start, init_weight));

    while (!priority_queue.empty())
    {
        // select the minimum weight from the priority queue
        const int vtx = priority_queue.top().vtx_;
        const int weight = priority_queue.top().weight_;
        priority_queue.pop();

        DPRINTF("vtx %d  weight %d\n", vtx, weight);

        if (weight > g_min_weight[vtx])
            continue;

        // find connected vertices
        vector<int> connectedVertices = edge.getConnectedVertices(vtx);

        // update min weight for the vertices
        for (int neighbour : connectedVertices)
        {
            const int updated_weight= weight + edge.getWeight(vtx, neighbour);

            if (updated_weight < g_min_weight[neighbour])
            {
                g_min_weight[neighbour] = updated_weight;
                priority_queue.push(VtxAndWeight(neighbour, g_min_weight[neighbour]));
            }

            DPRINTF("g_min_weight[%d] %d\n", neighbour, g_min_weight[neighbour]);
        }
    }

}


int main()
{
    cin >> g_num_of_vertex;
    cin.ignore();

    assert(kMaxVertex >= g_num_of_vertex);

    // init
    for (int i = 0; i < g_num_of_vertex; i++)
    {
        g_min_weight[i] = INT_MAX;
    }

    Edge edge(g_num_of_vertex);

    // input
    for (int i = 0; i < g_num_of_vertex; i++)
    {
        int from, degree;
        cin >> from >> degree;

        vector<int> tos, weights;

        for (int j = 0; j < degree; j++)
        {
            int to, weight;
            cin >> to >> weight;

            tos.push_back(to);
            weights.push_back(weight);

        }
        cin.ignore();

        edge.setWeight(from, tos, weights);
    }

#if MYDEBUG
    edge.printWeight();
#endif // MYDEBUG

    // process
    const int start = 0;
    calcShortestPath(start, edge);

    // output
    for (int i = 0; i < g_num_of_vertex; i++)
        printf("%d %d\n", i, g_min_weight[i]);

    return 0;
}