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 <stdio.h>
#include <string.h>
#include <iostream>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>

using namespace std;

typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;

const int iinf = 1 << 29;
const long long linf = 1ll << 61;

#define dump(x) cerr << #x << " : " << x << '\n'
#define MOD(x, y) (((y) + (x) % (y)) % (y))

int N;

int main(int argc, char* argv[])
{
	using COST_T = ll;
	using NODE_T = int;
	using PAIR_T = pair<COST_T, NODE_T>;

	struct Edge
	{
		NODE_T node;
		COST_T cost;
	};

	const int MAX_NODE_INDEX = 99;
	const COST_T INF_DIST = linf;
	vector<Edge> edges[MAX_NODE_INDEX + 1];
	COST_T dist_ar[MAX_NODE_INDEX + 1];

	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		int u, k;
		scanf("%d%d", &u, &k);
		for (int j = 0; j < k; j++) {
			int v, c;
			scanf("%d%d", &v, &c);
			edges[u].push_back( { v, c } );
		}
	}

	priority_queue<PAIR_T, vector<PAIR_T>, greater<PAIR_T>> pq;
	fill(dist_ar, dist_ar + MAX_NODE_INDEX + 1, INF_DIST);
	NODE_T st = 0;
	dist_ar[st] = 0;
	pq.push(PAIR_T(0, st));
	while(!pq.empty()) {
		COST_T temp_cost = pq.top().first;
		NODE_T node_index = pq.top().second;
		pq.pop();
		if (dist_ar[node_index] < temp_cost) continue;
		for (int next_list_index = 0; next_list_index < (int)edges[node_index].size(); next_list_index++) {
			COST_T new_cost = temp_cost + edges[node_index][next_list_index].cost;
			NODE_T next_index = edges[node_index][next_list_index].node;
			if (dist_ar[next_index] >= new_cost) {
				dist_ar[next_index] = new_cost;
				pq.push(PAIR_T(new_cost, next_index));
			}
		}
	}

	for (int i = 0; i < N; i++) {
		printf("%d %lld\n", i, dist_ar[i]);
	}

	return 0;
}

C++: #include <iostream>
#include<cstdio>
using namespace std;
const int INF = (1 << 21);
static int G[100][100];

void AskSSSP(int n){
    
    const int BLACK = 2,GRAY = 1,WHITE =  0;
    int color[n],d[n];
    for(int i = 0;i < n;++i){
        d[i] = INF;
        color[i] = WHITE;
    }
    d[0] = 0;
    int min,u;
    while(1){
        int min = INF;
        for(int i=0;i < n;++i){
            if(color[i] != BLACK && d[i] < min){
                min = d[i];
                u = i;
            }
        }
        if(min == INF) break;
        color[u] = BLACK;
        for(int i=0;i < n;++i){
            if(color[i] != BLACK && G[u][i] != INF){
                if(d[u] + G[u][i] < d[i]){
                    d[i] = d[u] + G[u][i];
                    color[i] = GRAY;
                }
            }
        }
        
    }
    for(int i = 0;i < n;++i) printf("%d %d\n",i,d[i]);

}

int main(void){
    int n,t,k,v,u;
    scanf("%d",&n);
    for(int i = 0;i < n;++i){
        for(int j = 0;j < n;++j){
            G[i][j] = INF;
        }
    }
    for(int i = 0;i < n;++i){
        scanf("%d %d",&t,&k);
        for(int j = 0;j < k;j++){
            scanf("%d %d",&v,&u);
            G[t][v] = u;
        }
    }
    AskSSSP(n);
    
}

C++: #include <bits/stdc++.h>
using namespace std;
#define inf 1e9+100

int n, m, u, k, v, c;
pair<int,pair<int,int> > e[10000];

// sからtに辿り着くまでに閉路が存在すればtrueを返す
// グラフに閉路が存在してもそこを経由できない場合は閉路を検出しない
bool bford(int n, pair<int,pair<int,int> > *e, int *d, int s, int t = -1) {
	fill(d, d+n, inf), d[s] = 0;
	for (int i=0; i<n*2; ++i) {
		for (int j=0; j<m; ++j) {
			int from = e[j].first, to = e[j].second.first, cost = e[j].second.second;
			if(d[from]!=inf && d[to]>d[from]+cost){
				d[to] = d[from] + cost;
				if(to==t && n-1<=i) return true;
			}
		}
	}
	return false;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> u >> k;
		for (int j = 0; j < k; ++j) {
			cin >> v >> c;
			e[m++] = {u, {v, c}};
		}
	}
	int d[100];
	if (bford(n,e,d,0)) cout << -1 << endl;
	else for (int i=0; i<n; ++i) cout << i << ' ' << d[i] << endl;
}