#include <bits/stdc++.h>
using namespace std;
static const int MAX_N = 100;
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;
static const int INF = 1<<21;
int M[MAX_N][MAX_N] = {0};
int d[MAX_N] = {0};
int color[MAX_N] = {WHITE};
int n,u,k,c,v;
void dijkstra(int s){
int mincost;
for(int u=0;u<n;u++){
color[u] = WHITE;
d[u] = INF;
}
d[s]=0;
color[0] = GRAY;
while(true){
mincost = INF;
int u = -1;
for(int i=0;i<n;i++){
if(color[i]!=BLACK && d[i]<mincost){
mincost = d[i];
u = i;
}
}
if(u==-1){
break;
}
color[u]=BLACK;
for(int v=0;v<n;v++){
if(color[v]!=BLACK && M[u][v]!=INF){
if(d[v]>d[u]+M[u][v]){
d[v]=d[u]+M[u][v];
color[v]=GRAY;
}
}
}
}
}
int main()
{
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
M[i][j] = INF;
}
}
for(int i=0;i<n;i++){
cin>>u>>k;
for(int j=0;j<k;j++){
cin>>c>>v;
M[u][c] = M[c][u] = v;
}
}
dijkstra(0);
for(int i=0;i<n;i++){
cout<<i<<" "<<d[i]<<endl;
}
return 0;
}