#include <iostream>
#include <vector>
#include <queue>
using namespace std;
static const int MAX = 10000;
static const int INFTY = (1<<21);

int main()
{
  int n;
  vector<pair<int,int>> adj[MAX];

  cin >> n;
  for (int i = 0; i < n; ++i)
  {
    int u, k;
    cin >> u >> k;
    for (int j = 0; j < k; ++j)
    {
      int v, c;
      cin >> v >> c;
      adj[u].emplace_back(v, c);
    }
  }

  priority_queue<pair<int,int>> PQ;
  int d[MAX];
  bool visited[MAX];
  for (int i = 0; i < n; ++i)
  {
    d[i] = INFTY;
    visited[i] = false;
  }
  d[0] = 0;
  PQ.emplace(0,0);

  while (!PQ.empty())
  {
    pair<int,int> f = PQ.top(); PQ.pop();
    int u = f.second;
    visited[u] = true;
    if (d[u] < f.first * (-1)) continue;

    for (int i = 0; i < adj[u].size(); ++i)
    {
      int v = adj[u][i].first;
      if (visited[v]) continue;
      if (d[v] > d[u] + adj[u][i].second)
      {
        d[v] = d[u] + adj[u][i].second;
        PQ.emplace(d[v] * (-1), v);
      }
    }
  }

  for (int i = 0; i < n; ++i)
  {
    cout << i << " " << d[i] << endl;
  }

  return 0;
}

