#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
#include <time.h>

#define BUF_SIZE 6000000
#define GRAPH_SIZE 10000
#define COST_MAX 100000

struct list {
  struct list *next;
  int dst;
  int cost;
};

struct list *create_graph(int num) {
  struct list *graph = malloc(sizeof(struct list)*num);
  int i;
  for(i = 0; i < num; i++) {
    graph[i].next = &graph[i];
  }
  return graph;
}

void insert(struct list *graph, int src, int dst, int cost) {
  struct list *head = &graph[src];
  struct list *elem = malloc(sizeof(struct list));
  elem->next = head->next;
  head->next = elem;
  elem->dst = dst;
  elem->cost = cost;
  return;
}

struct pair {
  int node;
  int cost;
};

#define HEAP_SIZE 100000
struct pair heap[HEAP_SIZE];
int pos = 1;

int is_empty(void) {
  return pos == 1;
}

void swap(struct pair *pa, struct pair *pb) {
  struct pair tmp = *pa;
  *pa = *pb;
  *pb = tmp;
}

// create min_heap
void enqueue(int node, int cost) {
  int idx = pos;
  struct pair p;
  p.node = node; p.cost = cost;
  heap[pos++] = p;
  int parent;
  while((parent = (idx>>1))) {
    if(heap[parent].cost > heap[idx].cost) {
      swap(&heap[parent], &heap[idx]);
      idx = parent;
    } else { break; }
  }
}

struct pair fetch_min(void) {
  struct pair res = heap[1];
  struct pair last = heap[--pos];
  int idx = 1;
  heap[idx] = last;
  // fix
  while(1) {
    int left = idx<<1;
    int right = left + 1;
    int smallest = idx;
    if(left < pos && heap[smallest].cost > heap[left].cost) {
      smallest = left;
    }
    if(right < pos && heap[smallest].cost > heap[right].cost) {
      smallest = right;
    }

    if(smallest != idx) {
      swap(&heap[smallest], &heap[idx]);
      idx = smallest;
    } else { break; }
  }
  return res;
}


int main(void) {
  int num;
  FILE *fp = stdin;
  static char line[BUF_SIZE];
  if(!fgets(line, BUF_SIZE, fp)) return 0;
  sscanf(line, "%d", &num);

  struct list *graph = create_graph(GRAPH_SIZE);

  int i, j;
  char *tmp;
  for(i = 0; i < num; i++) {
    if(!fgets(line, BUF_SIZE, fp)) return 0;
    tmp = strtok(line, " ");
    int u = strtol(tmp, NULL, 10);
    tmp = strtok(NULL, " ");
    int k = strtol(tmp, NULL, 10);
    for(j = 0; j < k; j++) {
      tmp = strtok(NULL, " ");
      int dst = strtol(tmp, NULL, 10);
      tmp = strtok(NULL, " ");
      int cost = strtol(tmp, NULL, 10);
      insert(graph, u, dst, cost);
    }
  }

  enqueue(0, 0);
  int min_cost[GRAPH_SIZE];
  min_cost[0] = 0;
  for(i = 1; i < num; i++) {
    min_cost[i] = GRAPH_SIZE*COST_MAX + 1; // be careful!!
  }

  int checked[GRAPH_SIZE] = {0};
  int cnt = 0;
  while(cnt < num && !is_empty()) {
    struct pair p = fetch_min();
    // don't search twice
    if(checked[p.node]) continue;
    checked[p.node] = 1;
    cnt++;

    // update which src is p.node
    struct list *head = &graph[p.node];
    struct list *tmp;
    for(tmp = head->next; tmp != head; tmp = tmp->next) {
      if(checked[tmp->dst]) continue;
      int new_cost = min_cost[p.node] + tmp->cost;
      if(new_cost < min_cost[tmp->dst]) {
        min_cost[tmp->dst] = new_cost;
        enqueue(tmp->dst, new_cost);
      }
    }
  }

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

  return 0;
}


Measured memory_bytes: 17552