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

#define BUF_SIZE 2000
#define GRAPH_SIZE 100
#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 1000
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/2)) {
    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 * 2;
    int right = idx * 2 + 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;
  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};
  while(!is_empty()) {
    struct pair p = fetch_min();
    checked[p.node] = 1;

    // update
    for(i = 0; i < num; i++) {
      if(!checked[i]) continue;
      struct list *head = &graph[i];
      struct list *tmp;
      for(tmp = head->next; tmp != head; tmp = tmp->next) {
        if(checked[tmp->dst]) continue;
        int new_cost = min_cost[i] + 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: 2032