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 <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 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,0 });
	int cnt = 0;
	while (pq.size() > 0) {
		if (cnt == n) break;
		vertex v = pq.top();
		pq.pop();
		if (color[v.id] == 1) continue;
		dist[v.id] = v.d;
		color[v.id] = 1;
		cnt++;
		Loop(j, E[v.id].size()) {
			pq.push({ E[v.id][j].end, dist[v.id] + E[v.id][j].w });
		}
	}
	Loop(i, n) {
		cout << i << " " << dist[i] << endl;
	}
	return 0;
}

C++: #include <iostream>
#include <vector>
#include <queue>
#define INF 1000000
using namespace std;

class vertex{
public:
  class edge{
  public:
    int to;
    int weight;
    edge(int to, int weight){
      this->to = to;
      this->weight = weight;
    }
  };

  vector<edge> edges;
  int num;
  int dis;

  vertex(){
    n++;
    vertexes.push_back(this);
  }

  bool operator< (const vertex& v) const{
    return dis < v.dis;
  }

  bool operator> (const vertex& v) const{
    return dis > v.dis;
  }

  static void dijkstra(int start){
    //距離の初期化
    for(int i=0; i<n; i++) vertexes[i]->dis=INF;
    vertexes[start]->dis=0;

    //プライオリティキューを初期化、始点を格納
    priority_queue<vertex, vector<vertex>, greater<vertex> > pq; pq.push(*vertexes[start]);


    while(!pq.empty()){
      vertex now = pq.top(); pq.pop(); //キューの先頭をポップ
      if(now.dis>vertexes[now.num]->dis) continue;

      //ポップしたキューの頂点集合について最短距離更新
      for(int i=0; i<now.edges.size(); i++){
        int newDis = now.dis+now.edges[i].weight;
        vertex* next = vertexes[now.edges[i].to];
        if(newDis < next->dis){
          next->dis = newDis;
          pq.push(*next);
        }
      }

    }


  }

  static void print(){
    for(int i=0; i<n; i++){
      cout << vertexes[i]->num << " " << vertexes[i]->dis << endl;
    }
  }
private:
  static int n;
  static vector<vertex*> vertexes;
};

int vertex::n=0;
vector<vertex*> vertex::vertexes;

int main(){
  int n; cin >> n;

  vertex graph[n];

  //入力を隣接リストのようなものに格納
  int v, k, to, weight;
  for(int i=0; i<n; i++){
    cin >> v >> k;
    graph[i].num=v;
    for(int j=0; j<k; j++){
      cin >> to >> weight;
      vertex::edge e(to, weight);
      graph[v].edges.push_back(e);
    }
  }

  vertex::dijkstra(0); //0始点のダイクストラ法

  vertex::print();

  return 0;
}

C++: #include<iostream>
#include<climits>
using namespace std;

typedef struct{
  int A[10005];
  int ans;
  bool c;
}node;
node T[10005];
int Q[100000000];
int head=0;
int tail=1;
int n;

void function(int num){
  while(true){
    if(head==tail)break;
    num=Q[head++];
    if(head==99999999)head=1;
    T[num].c=true;
    for(int i=0;i<n;i++){
      if(T[num].A[i]!=0){
	if(T[i].ans>T[num].ans+T[num].A[i]){
	  T[i].ans=T[num].ans+T[num].A[i];
	Q[tail++]=i;
	if(tail==99999999)tail=1;
	}
      }
    }
  }
}

int main(){
  int num,son,z,w;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>num>>son;
    T[num].ans=INT_MAX;
    for(int j=0;j<son;j++){
      cin>>z>>w;
      T[num].A[z]=w;
      }
  }
  Q[0]=0;
  T[0].ans=0;
  function(0);
 
  for(int i=0;i<n;i++){
      cout<<i<<" "<<T[i].ans<<endl;
  }
  return 0;
}