#include <iostream>
#include <queue>
#include <vector>
using namespace std;
    int d[10001];
    vector<int> G[500000],w[500000];
void DUK(int n){
    queue<int> q;
    int color[100000];
    for(int i=0;i<n;i++){
        d[i]=100000000;
        color[i]=0;
    }
    d[0]=0;
    q.push(0);
    color[0]=1;
    while(q.size()!=0){
        int u=q.front();
        q.pop();
        color[u]=0;
        for(int i=0;i<G[u].size();i++){
            int v=G[u][i];
            if(d[v]>d[u]+w[u][i]){
                d[v]=d[u]+w[u][i];
                if(color[v]==0){
                    q.push(v);
                    //color[v]=1;
                }
            }
        }
    }
}
int main(){
    int n,v,k,c,u;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>u>>k;
        for(int j=0;j<k;j++){
            cin>>v>>c;
            G[u].push_back(v);
            w[u].push_back(c);
        }
    }
    DUK(n);
    for(int i=0;i<n;i++){
        cout<<i<<" "<<d[i]<<endl;
    }
    return 0;
}


