Go: package main

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

const (
	MAX_N      = 10000
	MAX_WEIGHT = 100000
)

type Edge struct {
	start  int
	end    int
	weight int
}

type ShortestInfo struct {
	edges    []Edge
	shortest int
}

type Neighbor struct {
	node   int
	weight int
}

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

	n, err := nextInt(sc)
	if err != nil {
		panic(err)
	}

	shortestList := make([]ShortestInfo, n)
	for i := 1; i < n; i++ {
		shortestList[i] = ShortestInfo{edges: []Edge{}, shortest: MAX_N*MAX_WEIGHT + 1}
	}

	adjacentMatrix, err := createAdjacentMatrix(n, sc)
	if err != nil {
		panic(err)
	}

	sssp([]int{0}, shortestList, adjacentMatrix)
	for _, v := range shortestList {
		fmt.Printf("%d %d\n", v.getEnd(), v.shortest)
	}
}

func (si ShortestInfo) getEnd() int {
	if len(si.edges) == 0 {
		return 0
	} else {
		return si.edges[len(si.edges)-1].end
	}
}

func createAdjacentMatrix(n int, sc *bufio.Scanner) ([][]Neighbor, error) {
	adjacentMatrix := make([][]Neighbor, n)
	for i := 0; i < n; i++ {
		id, err := nextInt(sc)
		if err != nil {
			return nil, err
		}
		adjacentMatrix[id] = []Neighbor{}
		vertexNum, err := nextInt(sc)
		if err != nil {
			return nil, err
		}
		for j := 0; j < vertexNum; j++ {
			v, err := nextInt(sc)
			if err != nil {
				return nil, err
			}
			c, err := nextInt(sc)
			if err != nil {
				return nil, err
			}
			adjacentMatrix[id] = append(adjacentMatrix[id], Neighbor{v, c})
		}
	}
	return adjacentMatrix, nil
}

func sssp(nodeStack []int, shortestList []ShortestInfo, adjacentMatrix [][]Neighbor) {
	for len(nodeStack) > 0 {
		currentNode := nodeStack[0]
		nodeStack = nodeStack[1:]
		currentShortest := getShortest(currentNode, shortestList)
		adjacents := findAdjacents(currentNode, adjacentMatrix)
		for i := 0; i < len(adjacents); i++ {
			adj := adjacents[i]
			if currentShortest.shortest+adj.weight < getShortest(adj.end, shortestList).shortest {
				setShortest(adj.end, adj, currentShortest, shortestList)
				nodeStack = append(nodeStack, adj.end)
			}
		}
	}
}

func getShortest(node int, shortestList []ShortestInfo) ShortestInfo {
	return shortestList[node]
}

func setShortest(node int, edge Edge, currentShortest ShortestInfo, shortestList []ShortestInfo) {
	newEdges := make([]Edge, len(currentShortest.edges)+1)
	for i := 0; i < len(newEdges)-1; i++ {
		newEdges[i] = currentShortest.edges[i]
	}
	newEdges[len(newEdges)-1] = edge
	shortestInfo := ShortestInfo{edges: newEdges, shortest: currentShortest.shortest + edge.weight}
	shortestList[node] = shortestInfo
}

func findAdjacents(currentNode int, adjacentMatrix [][]Neighbor) []Edge {
	adjacents := adjacentMatrix[currentNode]
	edges := []Edge{}
	for _, neighbor := range adjacents {
		edges = append(edges, Edge{start: currentNode, end: neighbor.node, weight: neighbor.weight})
	}
	return edges
}

func nextInt(sc *bufio.Scanner) (int, error) {
	sc.Scan()
	return strconv.Atoi(sc.Text())
}

C++: #include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <list>
#include <stack>
#include <string>
#include <tuple>
#include <functional>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <map>
#include <random>
#include <cstdlib>
#define INT_MAX 2147483647
#define INT_MIN -2147483646
#define Loop(i, n) for(int i = 0; i < (int)n; i++)
#define Loop1(i, n) for(int i = 1; i <= (int)n; i++)
#define Loopr(i, n) for(int i = (int)n - 1; i >= 0; i--)
#define Loopr1(i, n) for(int i = (int)n; i >= 1; i--)
using namespace std;
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
void fastios() { ios_base::sync_with_stdio(0); cin.tie(0); }

static const int N = 10005;

struct vertex {
	int id;
	int p;
	int d;
	bool operator<(const vertex & another) const {
		return (d != another.d ? d>another.d : id>another.id);
	}
};

struct edge {
	int end;
	int w;
};

int main() {
	fastios();
	int n;
	cin >> n;
	vector<vector<edge>> E(N);
	Loop(i, n) {
		int u, k;
		cin >> u >> k;
		Loop(i, k) {
			int v, c;
			cin >> v >> c;
			E[u].push_back({ v,c });
		}
	}
	//
	priority_queue<vertex> pq;
	vi color(N, 0), dist(N, 0);
	pq.push({ 0,-1,0 });
	while (pq.size() > 0) {
		vertex v = pq.top();
		pq.pop();
		if (color[v.id] == 1) continue;
		dist[v.id] = v.d;
		color[v.id] = 1;
		Loop(j, E[v.id].size()) {
			pq.push({ E[v.id][j].end, v.id, dist[v.id] + E[v.id][j].w });
		}
	}
	Loop(i, n) {
		cout << i << " " << dist[i] << endl;
	}
	return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=100003;
const int INF=(1<<30);

int state[MAX],N,D[MAX];
vector<pair<int,int>> S[MAX];
priority_queue<pair<int,int>> Q;

void dijkstra(int u){
    int cnt=0;
    for(int i=0;i<N;i++){
        state[i]=0;
        D[i]=INF;
    }
    
    D[u]=0;
    Q.push(make_pair(0,u));
    
    while(1){
        int a=Q.top().second;
        Q.pop();
        if(state[a]==0){
            state[a]=1;
            for(int i=0;i<S[a].size();i++){
                if(state[S[a][i].first]==0){
                    Q.push(make_pair(-(D[a]+S[a][i].second),S[a][i].first));
                    D[S[a][i].first]=min(D[S[a][i].first],D[a]+S[a][i].second);
                }
            }
            cnt++;
        }
        if(cnt==N) break;
    }
    return;
}


int main(){

    cin>>N;
    for(int i=0;i<N;i++){
        int l,a;cin>>l>>a;
        for(int j=0;j<a;j++){
            int b,c;cin>>b>>c;
            S[i].push_back(make_pair(b,c));
        }
    }
    dijkstra(0);
    for(int i=0;i<N;i++){
        cout<<i<<" "<<D[i]<<endl;
    }
}

C++: #include<iostream>
#include<iomanip>
#include<algorithm>
#include<bitset>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<queue>
#include<vector>
using namespace std;

#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL

#define MAX 10000
#define WHITE 0
#define GRAY 1
#define BLACK 2

typedef pair<int, int> pii;

struct edge { int to, c; };
vector<edge> G[MAX];
int color[MAX] = {};//WHITE

int n;

void dijkstra() {
	priority_queue<pii, vector<pii>, greater<pii> >PQ; //minc v
	int color[MAX] = {};
	int	minc[MAX];
	fill(minc, minc + MAX, INF);
	minc[0] = 0;

	//?§????????????\
	PQ.push(pii(0, 0));
	color[0] = GRAY;

	//PQ???????´????????????°
	while (!PQ.empty()) {
		//minc???????°??????¨??????????´????????????????
		pii p = PQ.top(); PQ.pop();

		int u = p.second;
		color[u] = BLACK;

		//????????§???????????°??????
		if (minc[u] < p.first) { continue; }

		//??£??\????????????????????¨????????????
		for (int j = 0; j < G[u].size(); j++) {
			edge e = G[u][j];
			if (color[e.to] == BLACK)continue;
			if (minc[e.to] > minc[u] + e.c) {
				minc[e.to] = minc[u] + e.c;
				PQ.push(pii(minc[e.to], e.to));
				color[e.to] = GRAY;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		cout << i << " " << (minc[i] == INF ? -1 : minc[i]) << endl;
	}
}

int main() {
	cin >> 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);
			edge e; e.to = v; e.c = c;
			G[u].push_back(e);
		}
	}
	dijkstra();
	return 0;
}