Go: package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func main() {
	fp := os.Stdin
	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(os.Stdout)

	n := getNextInt(scanner)

	g := makeGraph(n)
	for i := 0; i < n; i++ {
		u := getNextInt(scanner)
		k := getNextInt(scanner)
		for ii := 0; ii < k; ii++ {
			v := getNextInt(scanner)
			c := getNextInt(scanner)
			g[u][v] = c
		}
	}

	ans := make([]int, n)
	im := make(IntMap, 1)
	im.increment(0)
	for len(im) < n {
		min := 1 << 30
		x := -1
		for u := range im {
			for v := 0; v < n; v++ {
				if im.get(v) != 0 {
					continue
				}
				if min > ans[u]+g[u][v] {
					min = ans[u] + g[u][v]
					x = v
				}
			}
		}
		im.increment(x)
		ans[x] = min
	}

	for i := 0; i < n; i++ {
		fmt.Fprintln(writer, fmt.Sprintf("%d %d", i, ans[i]))
	}
	writer.Flush()
}

func makeGraph(n int) [][]int {
	g := make([][]int, n)
	for i := 0; i < n; i++ {
		g[i] = make([]int, n)
		for ii := 0; ii < n; ii++ {
			g[i][ii] = 1 << 30
		}
	}

	return g
}

// IntMap ...
type IntMap map[int]int

func (m IntMap) get(key int) int {
	if _, ok := m[key]; ok {
		return m[key]
	}
	return 0
}
func (m IntMap) increment(key int) {
	if _, ok := m[key]; ok == false {
		m[key] = 0
	}
	m[key]++
}

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

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

    lp_queue<pair<Weight, size_t>> q; q.push(make_pair(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(make_pair(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;
}

C++: #include <iostream>
using namespace std;
static const int MAX = 100;
static const int INFTY = (1 << 21);
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

int n, M[MAX][MAX];

void dijkstra()
{
    int minv;
    int d[MAX], color[MAX];

    for (int i = 0; i < n; i++)
    {
        d[i] = INFTY;
        color[i] = WHITE;
    }

    d[0] = 0;
    color[0] = GRAY;
    while (1)
    {
        minv = INFTY;
        int u = -1;
        for (int i = 0; i < n; i++)
        {
            if (minv > d[i] && color[i] != BLACK)
            {
                u = i;
                minv = d[i];
            }
        }
        if (u == -1)
        {
            break;
        }
        color[u] = BLACK;
        for (int v = 0; v < n; v++)
        {
            if (color[v] != BLACK && M[u][v] != INFTY)
            {
                if (d[v] > d[u] + M[u][v])
                {
                    d[v] = d[u] + M[u][v];
                    color[v] = GRAY;
                }
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        cout << i << " " << (d[i] == INFTY ? -1 : d[i]) << endl;
    }
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            M[i][j] = INFTY;
        }
    }

    int k, c, u, v;
    for (int i = 0; i < n; i++)
    {
        cin >> u >> k;
        for (int j = 0; j < k; j++)
        {
            cin >> v >> c;
            M[u][v] = c;
        }
    }
    dijkstra();
    return 0;
}

C++: //#define LOCAL

#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;

#define rep(a, b) for(int i = a; i <= b; i++)
#define mst(a) memset(a, 0, sizeof(a))

const int MAX = 1e2 + 10;
const int INF = 0x3f3f3f3f;

int g[MAX][MAX];
int dist[MAX];
bool vis[MAX];

void init(int n)
{
	rep(0, n - 1)
	{
		dist[i] = INF;
		for(int j = 0; j < n; j++)
			g[i][j] = INF;
	}
	mst(vis);
	return;
}

void dijkstra(int n)
{
	rep(0, n - 1)
		dist[i] = INF;
	dist[0] = 0;
	rep(0, n - 1)
	{
		int mnidx = -1, mndist = INF;
		for(int j = 0; j < n; j++)
			if(!vis[j] && dist[j] < mndist)
				mnidx = j, mndist = dist[j];
		vis[mnidx] = true;
		for(int j = 0; j < n; j++)
			if(!vis[j])
				dist[j] = min(dist[j], dist[mnidx] + g[mnidx][j]);
	}
	return;
}

int main()
{

#ifdef LOCAL
	freopen("in.txt", "r", stdin);
#endif

	int n;
	while(~scanf("%d", &n))
	{
		init(n);
		rep(0, n - 1)
		{
			int u, v, w, num;
			scanf("%d%d", &u, &num);
			while(num--)
			{
				scanf("%d%d", &v, &w);
				g[u][v] = w;
			}
		}

		dijkstra(n);

		rep(0, n - 1)
			printf("%d %d\n", i, dist[i]);
	}
	return 0;
}

C++: #include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
using namespace std;
#define Test
const int MAX = 110000;
const int INF = 10000000;
vector<pair<int, int> > G[MAX];
int n;
int dis[MAX];
int vis[MAX];

void dij(int p) {
    for (int i = 0; i < n; i++) dis[i] = INF;
    memset(vis, false, sizeof(vis));
    dis[p] = 0;
    priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    pq.push(make_pair(0, p));
    while (!pq.empty()) {
        pair<int, int> pr = pq.top();
        pq.pop();
        int point = pr.second;
        if (vis[point]) continue;
        dis[point] = pr.first;
        vis[point] = true;
        for (int i = 0; i < G[point].size(); i++) {
            int pt = G[point][i].second;
            int v = G[point][i].first;
            if (!vis[pt] && dis[pt] > dis[point]+v) {
                dis[pt] = dis[point] + v;
                pq.push(make_pair(dis[pt], pt));
            }
        }
    }
}

int main() {
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int p, k;
        scanf("%d %d", &p, &k);
        while (k--) {
            int v, c;
            scanf("%d %d", &v, &c);
            G[p].push_back(make_pair(c, v));
        }
    }
    dij(0);
    for (int i = 0; i < n; i++) {
        printf("%d %d\n", i, dis[i]);
    }
    return 0;
}