Go: package main

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

const BIG_COST = 200000

const (
	ST_NOT_YET = iota
	ST_JOINED
)

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	nNodes := scanInt(sc)

	costs := make([][]int, nNodes)
	graph := make([][]int, nNodes)

	states := make([]int, nNodes)
	costSums := make([]int, nNodes)

	for i := 0; i < nNodes; i++ {
		costs[i] = make([]int, nNodes)
		costSums[i] = BIG_COST
	}

	for i := 0; i < nNodes; i++ {
		u := scanInt(sc)
		k := scanInt(sc)
		graph[u] = make([]int, k)
		for d := 0; d < k; d++ {
			v := scanInt(sc)
			graph[u][d] = v
			costs[u][v] = scanInt(sc)
		}
	}

	costSums[0] = 0
	for {
		minCost := BIG_COST
		var u int

		for i, cost := range costSums {
			if states[i] != ST_JOINED && cost < minCost {
				minCost = cost
				u = i
			}
		}

		if minCost == BIG_COST {
			break
		}

		states[u] = ST_JOINED

		for _, v := range graph[u] {
			cost := minCost + costs[u][v]
			if cost < costSums[v] {
				costSums[v] = cost
			}
		}
	}

	w := bufio.NewWriter(os.Stdout)
	for i, cost := range costSums {
		fmt.Fprintf(w, "%d %d\n", i, cost)
	}
	w.Flush()
}

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

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