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);
    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));
}

