void main(){
  import std.stdio, std.string, std.conv, std.algorithm;

  alias T=long;
  const inf=1e9.to!(T);
  struct Edge{int to; T cost;}
  int n; rd(n);
  auto g=new Edge[][](n);
  foreach(i; 0..n){
    auto args=readln.split.to!(int[]);
    foreach(j; 0..args[1]){
      g[i]~=Edge(args[j*2+2], args[j*2+3]);
    }
  }
  T[] dijkstra(Edge[][] g, int s){
    auto d=new T[](n);
    fill(d, inf);
    struct P{int v; T d;}
    import std.container;
    // auto Q=new RedBlackTree!(P, "a.d<b.d", true);
    auto Q=new MyBinaryHeap!(P, "a.d<b.d");
    Q.insert(P(s, 0)); d[s]=0;
    while(Q.empty==false){
      auto cur=Q.front; Q.removeFront;
      foreach(e; g[cur.v]){
        if(d[e.to]<=d[cur.v]+e.cost) continue;
        d[e.to]=d[cur.v]+e.cost;
        Q.insert(P(e.to, d[e.to]));
      }
    }
    return d;
  }

  auto d=dijkstra(g, 0);
  foreach(i; 0..n) writeln(i, " ", d[i]);
}

void rd(T...)(ref T x){
  import std.stdio, std.string, std.conv;
  auto l=readln.split;
  assert(l.length==x.length);
  foreach(i, ref e; x) e=l[i].to!(typeof(e));
}

import std.functional : binaryFun;
class MyBinaryHeap(T, alias less = "a<b") if(is(typeof(binaryFun!less(T.init, T.init))))
{
  import std.exception : enforce;
  import std.algorithm : each, swap;
  import std.functional : binaryFun;

  private T[] dat;
  private alias comp = binaryFun!(less);
  this()
  {
  }

  this(T[] arr)
  {
    arr.each!(x => insert(x));
  }

  void insert(T x)
  {
    size_t i = dat.length;
    dat ~= x;
    while (i > 0)
    {
      size_t p = (i - 1) / 2;
      if (comp(dat[i], dat[p]))
      {
        swap(dat[i], dat[p]);
        i = p;
      }
      else
      {
        break;
      }
    }
  }

  T front()
  {
    enforce(dat.length > 0, "Cannot call front on an empty heap."); // https://github.com/dlang/phobos/blob/master/std/container/binaryheap.d#L248
    return dat[0];
  }

  void removeFront()
  {
    enforce(dat.length > 0, "Cannot call removeFront on an empty heap."); // https://github.com/dlang/phobos/blob/master/std/container/binaryheap.d#L316
    swap(dat[0], dat[$ - 1]);
    dat = dat[0 .. ($ - 1)];
    size_t len = dat.length;
    size_t i = 0;
    while (i * 2 + 1 < len)
    {
      if (i * 2 + 2 < len)
      {
        size_t j = comp(dat[i * 2 + 1], dat[i * 2 + 2]) ? i * 2 + 1 : i * 2 + 2; // 左右で強いほうの子と比べる
        if (comp(dat[j], dat[i]))
        {
          swap(dat[j], dat[i]);
          i = j;
        }
        else
        {
          break;
        }
      }
      else
      { // 左の子しかない
        if (comp(dat[i * 2 + 1], dat[i]))
        {
          swap(dat[i * 2 + 1], dat[i]);
          i = i * 2 + 1;
        }
        else
        {
          break;
        }
      }
    }
  }
  bool empty(){
    return dat.length==0;
  }
}

