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
}

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{1}, shortestList, adjacentMatrix)
	for _, v := range shortestList {
		fmt.Printf("%d %d\n", v.getEnd()-1, v.shortest)
	}
}

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

func createAdjacentMatrix(n int, sc *bufio.Scanner) ([][]int, error) {
	adjacentMatrix := make([][]int, n)
	for i := 0; i < n; i++ {
		id, err := nextInt(sc)
		if err != nil {
			return nil, err
		}
		adjacentMatrix[id] = make([]int, n)
		for j := 0; j < n; j++ {
			adjacentMatrix[id][j] = -1
		}
		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][v] = c
		}
	}
	return adjacentMatrix, nil
}

func sssp(nodeStack []int, shortestList []ShortestInfo, adjacentMatrix [][]int) {
	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-1]
}

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-1] = shortestInfo
}

func findAdjacents(currentNode int, adjacentMatrix [][]int) []Edge {
	adjacents := adjacentMatrix[currentNode-1]
	edges := []Edge{}
	for i, v := range adjacents {
		if v > 0 {
			edges = append(edges, Edge{start: currentNode, end: i + 1, weight: v})
		}
	}
	return edges
}

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

C++: #include <stdio.h>
#include <iostream>
#include <queue>
using namespace std;

#define NIL -1
#define INF 100000000
#define WHITE 1
#define GREY 2
#define BLACK 3
#define N_MAX 10000

int G[N_MAX][N_MAX];
int V[N_MAX];
int V_value[N_MAX];

void init(){
    for(int i = 0; i < N_MAX; i++){
        V[i] = WHITE;
        V_value[i] = INF;
    }

    for(int i = 0; i < N_MAX; i++){
        for(int j = 0; j < N_MAX; j++){
            G[i][j] = NIL;
        }
    }
}

int main(void){
    init();
    int n;
    scanf("%d\n", &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);
            G[u][v] = c;
        }
    }

    priority_queue<pair<int, int>> PQ;

    V[0] = BLACK;
    V_value[0] = 0;
    int new_node = 0;
    
    while(1){
        //printf("new_node: %d\n", new_node);
        for(int i = 0; i < n; i++){
            if(G[new_node][i] != NIL && V[i] == WHITE){
                V_value[i] = min(V_value[i], V_value[new_node] + G[new_node][i]);
                //printf("push %d %d\n",i,  V_value[i]);
                PQ.push(make_pair(V_value[i] * (-1), i));
            }
        }

        int min_value;
        int min_index = NIL;
        while(!PQ.empty()){
            pair<int, int> p = PQ.top(); PQ.pop();
            //printf("pop %d %d\n", p.second, p.first * (-1));
            if(p.first * (-1) == V_value[p.second] && V[p.second] == WHITE){
                min_value = p.first * (-1);
                min_index = p.second;
                break;
            }
        }

        if(min_index == NIL)
            break;

        new_node = min_index;
        V[new_node] = BLACK;
        V_value[new_node] = min_value;
    }
    
    for(int i = 0; i < n; i++){
        printf("%d %d\n", i, V_value[i]);
    }

    return 0;
}

C++: //By Vlgd
#include<bits/stdc++.h>
using namespace std;
const int N=10000;
const int INF=(1<<21);
struct edge{int w,v;};
struct path{int l,v;};
vector<edge>G[N];
int n,vis[N]={0},dis[N];
//priority_queue<path>pq;
path H[10*N];int h=0;
bool isempty(){return h==0;}
void insert(path p){
	int i=++h;
	H[i]=p;
	while(i>1&&H[i].l<H[i/2].l){
		swap(H[i],H[i/2]);
		i/=2;
	}
}
void heapify(int i){
	int les;
	if(i*2<=h&&H[i].l>H[2*i].l) les=2*i;
	else les=i;
	if(i*2+1<=h&&H[les].l>H[i*2+1].l) les=2*i+1;
	if(les!=i){
		swap(H[i],H[les]);
		heapify(les);
	}
}
path extract(){
	path p=H[1];
	H[1]=H[h--];
	if(h>1) heapify(1);
	return p;
} 
//
void dij(int s){
	for(int i=0;i<n;i++) dis[i]=INF;
	path p;
	dis[s]=0;
	p.l=0;p.v=0;
	insert(p);
	while(!isempty()){
		p=extract();
		int u=p.v;
		vis[u]=1;
		for(int i=0;i<G[u].size();i++){
			int v=G[u][i].v;
			int w=G[u][i].w;
			if(!vis[v]){
				if (dis[v]>dis[u]+w){
					p.l=dis[v]=dis[u]+w;
					p.v=v;
					insert(p);
				}
			}
		}
	}
}
int main(){
	scanf("%d",&n);
	int u,deg;edge e;
	for (int i=0;i<n;i++){
		scanf("%d%d",&u,&deg);
		for(int j=0;j<deg;j++){
			scanf("%d%d",&e.v,&e.w);
			G[u].push_back(e);
		}
	}
	dij(0);
	for (int i=0;i<n;i++) printf("%d %d\n",i,dis[i]);
	return 0;
}

C++: #include<stdio.h>
#define min(a,b) ((a)>(b))?(b):(a)
int main(void){
	int i,j,n,u,k,s,tmp,w,adj[100][100]={0};
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d %d",&u,&k);
		for(j=0;j<k;j++){
			scanf("%d %d",&tmp,&w);
			adj[u][tmp]=w;
		}
	}
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			if((adj[i][j]==0) && (i!=j)){
				adj[i][j]=100000000;
			}
		}
	}
	for(s=0;s<n;s++){
		for(i=0;i<n;i++){
			for(j=0;j<n;j++){
				adj[i][j]=min(adj[i][j],adj[i][s]+adj[s][j]);
			}
		}
	}
	for(i=0;i<n;i++){
		printf("%d %d\n",i,adj[0][i]);
	}
	return 0;
}

C++: #include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

const int INF = 0xfffffff;
const int MAX = 10000;

struct Edge {
	Edge() {};
	Edge(int v, int c) :v(v), c(c) {};
	bool operator < (const Edge& e)const {
		return c > e.c;
	}
	int v;
	int c;
};

int main() {
	int n;
	priority_queue<Edge> graph[MAX];
	vector<Edge> table;
	bool check[MAX] = { false };
	int ary[MAX] = { 0 };

	cin >> n;

	for (int i = 0; i < n; i++) {
		int u, k;
		cin >> u >> k;
		for (int j = 0; j < k; j++) {
			Edge e;
			cin >> e.v >> e.c;
			graph[u].push(e);
		}
	}

	Edge e(0, 0);
	table.push_back(e);
	check[0] = true;

	for (int i = 1; i < n; i++) {
		Edge minv(0, INF);
		int erase = 0;

		for (int j = 0; j < table.size(); j++) {
			int v = table[j].v;
			int c = table[j].c;	
			while (!graph[v].empty() && check[graph[v].top().v])graph[v].pop();
			if (graph[v].empty())continue;
			if (c + graph[v].top().c < minv.c) {
				minv.c = c + graph[v].top().c;
				minv.v = graph[v].top().v;
				erase = v;
			}
		}
		table.push_back(minv);
		check[minv.v] = true;
		graph[erase].pop();
	}
	
	for (int i = 0; i < n; i++) {
		ary[table[i].v] = table[i].c;
	}
	for (int i = 0; i < n; i++) {
		cout << i << " " << ary[i] << endl;
	}

	return 0;
}