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 <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define fi first
#define se second
#define mp make_pair
#define itrfor(itr,A) for(auto itr = A.begin(); itr !=A.end();itr++)
#define dame { printf("No\n"); return 0;}
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
typedef long long llong;
char moji[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
char moji2[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
char moji3[10]={'0','1','2','3','4','5','6','7','8','9'};
#define Sort(a) sort(a.begin(),a.end());
#define Reverse(a) reverse(a.begin(),a.end());
#define print(a) cout << a << endl;
#define MOD llong(1e9+7)
#define MAX int(2 * 1e5 +5)
#define debug(x)  cout << #x << " = " << (x) << endl;
#define pi acos(-1.0)
#define int llong
#define INF llong(1e17)


template <typename T> class Dijkstra{
    vector<pair < T, int >>* edges;
    int* par;
    T* Distance;
    int size;

public:
    Dijkstra(int n){
        size = n;
        edges = new vector<pair<T , int> >[n];
        Distance = new T[n];
        par = new int[n];
    };

    T Get_Distance(int x){
        if(x < 0 or x>= size) return T(-1);
        else return Distance[x];
    };

    void add_edge(T dist, int s,int t);

    void Disp_Graph();

    void Get_Shortest(int s);



};


template<typename T> void Dijkstra<T>::add_edge(T dist, int s,int t){
    edges[s].push_back( mp(dist, t));
}

template<typename T> void Dijkstra<T>::Disp_Graph(){
    REP(i,size){
        REP(j,edges[i].size()){
            cout << edges[i][j].se << " " << edges[i][j].fi <<endl;
        }
        cout << endl;
    }
}


template<typename T> void Dijkstra<T>::Get_Shortest(int s){
    REP(i,size) Distance[i] = T(INF);
    reversed_priority_queue< pair<T, int > > Q;
    bool used[size];
    REP(i,size) used[i] = false;
    REP(i,size) par[i] = -1;
    int Q_size = 1;
    Distance[s] = 0;
    Q.push( mp(T(0),s ) );
    while(Q_size){
        pair < T, int > x = Q.top();
        Q.pop();
        Q_size --;
        if( used[x.se]) continue;
        used[x.se] = true;
        REP(i,edges[x.se].size()){
            pair < T, int > y = edges[x.se][i];
            if(  Distance[y.se] > Distance[x.se] + y.fi){
                Distance[y.se] = Distance[x.se] + y.fi;
                Q.push( mp ( Distance[y.se],y.se) );
                Q_size ++;
                par[y.se] = x.se;
            }
        }

    }

}











signed main(){
    int n,m,s;
    cin >> n;
    Dijkstra<int> D(n);
    int t1,d1;
    REP(i,n){
        int u,k;
        scanf("%lld%lld",&u,&k);
        REP(j,k){
            scanf("%lld%lld",&t1,&d1);
            D.add_edge(d1,u,t1);
        
        }
    }


    D.Get_Shortest(0);
    int tmp = 0;
    REP(i,n){
        printf("%lld %lld\n",i,D.Get_Distance(i));
    }
}