#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define N 10005
#define BLACK -2
#define WHITE 1
#define GRAY 7
#define INF INT_MAX
#define NIL -5

typedef struct {
  int color, d, pi, id, check; //minDistoMST, idxinH;  
}Vertex;


typedef struct{
  int weight, to;
}Edge;



//void Insert(int, int);
void MinHeapify(int);
void buildMinHeap();
Vertex* Extract();
void HeapDecrease(int, int);
void dijkstra(int);



int adj[N][N], node_size[N]; // 隣接リストの数
int hsize, n;
Vertex data[N], *heap[N];
Edge **node; //隣接リスト


int main () {
  int m, i, j, sum =0, tmp[N], k = 0, p = 0, l = 0, q = 0;
  Edge new;

  node = (Edge**)malloc(sizeof(Edge *) * N);
  
  scanf("%d",&n);

  for(i = 0 ; i < n ; i++) {
    scanf("%d %d",&p, &m);


    node_size[p] = m;
    node[p] = (Edge *)malloc(sizeof(Edge) * m);    
    for(j = 0 ; j < m ; j++) {
      scanf("%d %d",&l, &q);

      node[p][j].weight = q;
      node[p][j].to = l;
      //adj[i][j] = m;

    }

    
  }

  /*
  for (i = 0; i < n; i++ ){
    printf("node size %d\n", node_size[i]);
    for (j = 0; j < node_size[i]; ++j) {
      printf("weight %d\n", node[i][j].weight);
    }
  }
  */
  dijkstra(0);

  for(i = 0 ; i< n ; i++) {
    printf("%d %d\n", i,data[i].d);
    
  }

  return 0;
}



void dijkstra(int r) {
  int i, f = 0, min = 0;
  Vertex u;
  Edge edge;
  for(i = 0 ; i < n ; i++) {
    data[i].color = WHITE;
    data[i].d = INF;
    //if(i == r) data[i].d = 0;
    data[i].pi = NIL;
    data[i].id = i;
    //data[i].idxinH = i;
    //data[i].minDistoMST = INF;
    heap[i+1] = &data[i];
    data[i].check = i + 1;
    //Insert(INF,i);
  }

  data[r].d = 0;
  
  

  hsize = n; 
  buildMinHeap();

  
  while(hsize > 0) {
    f = 0;
    u = *Extract();

    data[u.id].color = BLACK;
    //printf("u.id: %d\n",u.id);

    //無視する
    min = INF;
    for(i = 0 ; i < node_size[u.id] ; i++) {
      if(node[u.id][i].weight < min) min = node[u.id][i].weight;
    }

    if(min == INF) continue;

    for(i = 0 ; i < node_size[u.id] ; i++) {
      edge = node[u.id][i];
      //printf("edge.to: %d, edge:weight %d\n", edge.to, edge.weight);
      /*if(data[u.id].d < data[edge.to].d) {
	f = 1;
	continue;

	}*/
     
      /*	if(adj[u][i] < data[i].d) {
	  data[i].pi = u;
	  data[i].d = adj[u][i];
	  printf("from %d to %d connected (cost %d)\n", u, i, data[i].d); 
	  HeapDecrease(i, adj[u][i]);
	}
      */

      //printf("edge to: %d, cost: %d, update: %d\n", edge.to, data[edge.to].d, data[u.id].d + edge.weight);
      if(data[edge.to].check >= 1 && data[edge.to].color != BLACK)
	if(data[u.id].d + edge.weight < data[edge.to].d) {
	  data[edge.to].d = data[u.id].d + edge.weight;
	  data[edge.to].color = GRAY;
	  HeapDecrease(edge.to, edge.weight+data[u.id].d);
      }
    }
  }
}











/*void Insert(int x, int y) {
  int i;
  

  hsize++;

  data[hsize].d = y;
  

  //if(hsize > 1) node[hsize].pk = hsize/2;  
  

  }*/





Vertex* Extract() {
  Vertex * min;
  
  
  if(hsize < 1) return 0;


  min = heap[1];
  //heap[1]->id = -1;
  heap[1]->check = 0;
  heap[hsize]->check = 1;
  heap[1] = heap[hsize];
  
  hsize--;
  MinHeapify(1);

  return min;
}










void MinHeapify(int x) {
  int left = 2 * x, right = 2 * x + 1, small = 0, tmp1 = 0;
  Vertex * tmp;

  
  if(left <= hsize && heap[left]->d < heap[x]->d) small = left;
  
  else small = x;
  
  if(right <= hsize && heap[right]->d < heap[small]->d) small = right;

  if(small != x) {
    /*tmp = node[x];
    node[x] = node[small];
    node[small] = tmp;*/
    
    heap[x]->check = small;
    heap[small]->check = x;
    /* tmp1 = heap[small]->check;
    heap[small]->check = heap[x]->check;
    heap[x]->check = tmp1;*/
    
    
    tmp = heap[small];
    heap[small] = heap[x];
    heap[x] = tmp;

    
    MinHeapify(small);
  }
 
}


void buildMinHeap() {
  int i;
  
  for(i = hsize/2 ; i >= 1 ; i--) MinHeapify(i);
}




void HeapDecrease(int j, int k) {
  Vertex *tmp;
  int i, tmp1;

  i = data[j].check;
  if(k > heap[i]->d) return;

  heap[i]->d = k;

  while(i > 1 && heap[i/2]->d > heap[i]->d) {
    /*tmp1 = node[node[i].pk].weight;
    tmp2 = node[node[i].pk].key;
    node[node[i].pk].weight = node[i].weight;
    node[node[i].pk].key = node[i].key;
    node[i].weight = tmp1;
    node[i].key = tmp2; */ 

    heap[i]->check = i/2;
    heap[i/2]->check = i;
    /*tmp1 = heap[i]->check;
    heap[i]->check = heap[i/2]->check;
    heap[i/2]->check = tmp1; */
    
    tmp = heap[i/2];
    heap[i/2] = heap[i];
    heap[i] = tmp;
    i = i/2;
  }
}



Measured memory_bytes: 5656