#include<bits/stdc++.h>
using namespace std;
static const int MAX=10000;
static const int INF=(1<<20);
static const int W=0;
static const int G=1;
static const int B=2;
int n;
vector<pair<int,int> >adj[MAX];
void dijkstra(){
  priority_queue<pair<int,int> >pq;
  int color[MAX];
  int d[MAX];
  for(int i=0;i<n;i++){
    d[i]=INF;
    color[i]=W;
  }
  d[0]=0;
  pq.push(make_pair(0,0));
  color[0]=G;
  while(!pq.empty()){
    pair<int,int>f=pq.top();
    pq.pop();
    int u=f.second;
    color[u]=B;
    if(d[u]<f.first*(-1)) continue;
    for(int j=0;j<adj[u].size();j++){
      int v=adj[u][j].first;
      if(color[v]==B) continue;
      if(d[v]>d[u]+adj[u][j].second){
	d[v]=d[u]+adj[u][j].second;
	pq.push(make_pair(d[v]*(-1),v));
	color[v]=G;
      }
    }
  }
  for(int i=0;i<n;i++){
    cout<<i<<" "<<(d[i]==INF ? -1 : d[i])<<endl;
  }
}
int main(){
  int k,u,v,c;
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    scanf("%d %d",&u,&k);
    for(int j=0;j<k;j++){
      scanf("%d %d",&v,&c);
      adj[u].push_back(make_pair(v,c));
    }
  }
  dijkstra();
  return 0;
}
      
