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()

	route := make([][]Node, n)
	weight := make([]int, n)
	for i := 0; i < n; i++ {
		weight[i] = NIL
	}

	for i := 0; i < n; i++ {
		u := scanInt()
		k := scanInt()
		route[i] = make([]Node, k)
		for j := 0; j < k; j++ {
			route[u][j] = Node{id: scanInt(), weight: scanInt()}
		}
	}

	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 _, nextNode := range route[node.id] {
			if weight[nextNode.id] != NIL {
				continue
			}
			nextNode.weight += node.weight
			heap.Push(h, nextNode)
		}
	}

	for i, w := range weight {
		fmt.Println(i, w)
	}
}

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

using Weight=int;
struct Edge {
    int src,dest; Weight weight;
    bool operator<(const Edge &rhs)const{
        return weight<rhs.weight;
    }
};
using Edges=vector<Edge>;
using Graph=vector<Edges>;

const Weight INF=1e9;

void dijkstra(const Graph &g,int s,vector<Weight> &d)
{
    assert(0<=s && s<g.size());
    d.assign(g.size(),INF); d[s]=0;
    vector<int> used(g.size(),0);
    using P=pair<Weight,int>;
    priority_queue<P,vector<P>,greater<P>> que;
    que.push({0,s});
    while(!que.empty())
    {  
        auto val=que.top(); que.pop();
        Weight dist=val.first;
        int v=val.second;
        if(used[v]) continue;
        used[v]=true;
        for(auto e:g[v])
        {
            int to=e.dest;
            Weight w=e.weight;
            if(dist+w<d[to])
            {
                d[to]=dist+w;
                que.push({d[to],to});
            }
        }
    }
}

int main()
{
    int n;
    cin>>n;
    Graph g(n);
    for(int i=0;i<n;i++)
    {
        int k;
        cin>>k>>k;
        for(int j=0;j<k;j++)
        {
            int v;
            cin>>v;  
            Weight c;
            cin>>c;          
            g[i].push_back((Edge){i,v,c});
        }
    }
    vector<Weight> d;
    dijkstra(g,0,d);
    for(int i=0;i<n;i++)
    {
        cout<<i<<" "<<d[i]<<endl;
    }
    return 0;
}

C++: #include <iostream>
#include <vector>
#include <climits>
#include <queue>

using namespace std;

const int kSize = 100001;

vector<int> V;

struct Node {
    int to;
    int weight;

    Node(int _to, int _weight) {
        to = _to;
        weight = _weight;
    }
};

int n;
vector<Node> adj[kSize];
bool isMarked[kSize];
int tree[kSize];
int dis[kSize];

void Dijkstra(int s) {
    dis[s] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<> > pq;

    pq.push(make_pair(s, 0));
    //isMarked[s] = true;
    tree[s] = s;

    while (!pq.empty()) {
        pair<int, int> p = pq.top();
        pq.pop();
        int from = p.first;
        for (int i = 0; i < adj[from].size(); ++i) {
            int to = adj[from][i].to;
            if (dis[from] + adj[from][i].weight < dis[to]) {
                dis[to] = dis[from] + adj[from][i].weight;
                tree[to] = from;
                pq.push(make_pair(to, dis[to]));
            }
        }
    }

}

int main() {
    fill(isMarked, isMarked + kSize, false);
    fill(dis, dis + kSize, INT_MAX);
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int u, k;
        cin >> u >> k;
        for (int j = 0; j < k; ++j) {
            int v, c;
            cin >> v >> c;
            adj[u].emplace_back(v, c);
        }
    }

    Dijkstra(0);
    for (int i = 0; i < n; ++i) {
        cout << i << " " << dis[i] << endl;
    }
}

C++: #include<bits/stdc++.h>
using namespace std;
static const int INF=1000000;

int n;
vector<pair<int,int> > nex[10000];

void dijkstra(){ 
  priority_queue<pair<int,int> >PQ;
  int d[10000];
  int color[10000];  
  for(int i=0;i<n;i++){
    d[i]=INF;
    color[i]=0;
  }
  
  color[0]=1;
  d[0]=0;
  PQ.push(make_pair(0, 0));
  
  while( !PQ.empty() ){
    pair<int,int> f = PQ.top();PQ.pop();
    int u =f.second;
    color[u]=2;
    if(d[u] < f.first *(-1)) continue;
    
    for(int j=0;j<nex[u].size();j++){
      int v=nex[u][j].first;
      if(color[v] == 2) continue;
      if(d[v]>d[u]+nex[u][j].second){
        d[v]=d[u]+nex[u][j].second;
        PQ.push(make_pair(d[v]*(-1),v));
        color[v]=1;
      }
    }
  }
  for(int i=0;i<n;i++){
    cout<<i<<" "<<(d[i] == INF ?:d[i])<<endl;
  }
}


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

C++: #include <vector>
#include <queue>
#include <stdio.h>
#include <iostream>
#include <limits>

using namespace std;

const int MAXN = 10000;
const int INF = numeric_limits<int>::max();

vector< pair<int, int> > G[MAXN];
int dist[MAXN];
int n;

void dijkstra(int start) {
  for (int i = 0; i < n; ++i) dist[i] = INF;

  priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > q;
  q.emplace(0, start);
  dist[start] = 0;
  while (!q.empty()) {
    pair<int, int> cur = q.top(); q.pop();
    int v = cur.second;
    int cost = cur.first;
    if (dist[v] < cost) continue;

    for (size_t i = 0; i < G[v].size(); ++i) {
      int u = G[v][i].first;
      int new_cost = G[v][i].second + cost;
      if (dist[u] > new_cost) {
	q.emplace(new_cost, u);
	dist[u] = new_cost;
      }
    }
  }
}
int main () {
  cin >> n;

  for (int i = 0; i < n; ++i) {
    int u, k;
    cin >> u >> k;
    for (int j = 0; j < k; ++j) {
      int v, c;
      cin >> v >> c;
      G[u].emplace_back(v, c);
    }
  }
  dijkstra(0);
  for (int i = 0; i < n; ++i) {
    cout << i << " " << dist[i] << endl;
  }
  return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
struct edge{
  int to,cost;
};
typedef pair<int,int> P;
int V;
vector<edge> G[100000];
int d[100000];
void dijkstra(int s){
  priority_queue<P ,vector<P>,greater<P> >que;
  fill(d,d+V,1e9+1);
  d[s]=0;
  que.push(P(0,s));
  //
  while(!que.empty()){
    P p=que.top();
    que.pop();
    int v=p.second;
    if(d[v]<p.first)continue;

    for(int i=0;i<G[v].size();i++){
      edge e=G[v][i];
      if(d[e.to]>d[v]+e.cost){
        d[e.to]=d[v]+e.cost;
        que.push(P(d[e.to],e.to));
      }
    }
  }
}
int main(){
  int k,u,v,c;
  cin >> V;
  for(int i=0;i<V;i++){
    cin >> u >> k;
    for(int j=0;j<k;j++){
      cin >> v >> c;
      edge ed;
      ed.to=v;
      ed.cost=c;
      G[u].push_back(ed);
    }
  }
  dijkstra(0);
  for(int i=0;i<V;i++){
    cout << i << " " << d[i] << endl;
  }
  return 0;
}