//config = { input: 'tmp', newline: '\r\n' }; // win
config = { input: '/dev/stdin', newline: '\n' }; // linux

line = require('fs').readFileSync(config.input, 'ascii')
  .trim()
  .split(config.newline);
n = Number(line.shift());
adj = {};
function add(obj, u, v, c) {
  if (!obj.hasOwnProperty(u)) obj[u] = {};
  obj[u][v] = c;
}
for (i in line) {
  ary = line[i].split(' ').map(Number);
  u = ary[0];
  for (j = 2; j < ary.length; j += 2)
    add(adj, u, ary[j], ary[j+1]);
}

visited = new Array(n);
for (i = 0; i < n; i++) visited[i] = false;

function dfs(from, to) {
  var min = Number.MAX_VALUE, i;
  if (from == to) return 0;
  if (visited[from]) return Number.MAX_VALUE;
  visited[from] = true;
  for (i in adj[from]) {
    min = Math.min(min, adj[from][i] + dfs(i, to));
  }
  visited[from] = false;
  return min;
}

for (i = 0; i < n; i++) console.log('%d %d', i, dfs(0, i));