#include<bits/stdc++.h>
using namespace std;
using ll = long long;

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define br() p("")
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("Yes")
#define p_no() p("No")

const ll mod = 1e9 + 7;
const ll inf = 1e18;

template < typename T >
void vprint(T &V){
	for(auto v : V){
    	cout << v << " ";
	}
	cout << endl;
}

struct Edge{
    ll to;
    ll cost;
    Edge(ll to, ll cost): to(to), cost(cost) {}
    Edge(){
        to = 0;
        cost = 0;
    }
};

struct Node{
    ll distance;
    ll index;
    Node(ll d, ll i){
        distance = d;
        index = i;
    }
    Node(){}

    bool operator<(const Node &another) const
    {
        return distance < another.distance;
    }
    bool operator>(const Node &another) const
    {
        return distance > another.distance;
    }
};

struct Dijkstra{
    vector<ll> d;
    vector<vector<Edge> > graph;
    vector<bool> done;

    // ノード数を入れる
    void initialize(ll size){
        d.resize(size);
        done.resize(size);
        graph.resize(size);
        reset();
    }

    void reset(){
        ll N = graph.size();
        FOR(i, 0, N){
            d[i] = inf;
            done[i] = false;
        }
    }
    
    ll distance(int i){
        if(d.size()<=i) return -1;
        return d[i];
    }

    void print_graph(){
        FOR(i, 0, graph.size()){
            cout << i << " -> ";

            for(auto edge : graph[i]){
                cout << edge.to << " ";
            }
            cout << endl;
        }
        p("distance");
        FOR(i, 0, graph.size()){
            ll d = distance(i);
            cout << i << " " << d << endl;
        }
    }

    void register_edge(ll a, ll b, ll cost){
        auto edge = Edge(b, cost);
        graph[a].push_back(edge);
    }

    void calc_shortest_path(ll from=0){
        priority_queue<Node, vector<Node>, greater<Node> > que;
        auto node = Node();
        // 始点
        node.index = from;
        node.distance = 0;
        que.push(node);

        while(!que.empty()){
            // 1番distanceが小さいノード
            Node n = que.top();
            que.pop();

            if(done[n.index]){
                continue;
            }
            
            done[n.index] = true;
            d[n.index] = n.distance;

            auto edge_list = graph[n.index];
            for(auto edge : edge_list){   
                // 短くなるノードがあれば
                if(!done[edge.to] && n.distance + edge.cost < d[edge.to]){
                    ll shorter_distance = n.distance + edge.cost;
                    que.push(Node(shorter_distance, edge.to));
                }
            }
        }
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N;
    cin >> N;

    auto dij = Dijkstra();
    dij.initialize(N);

    FOR(i, 0, N){
        ll hoge; cin >> hoge;
        ll k; cin >> k;
        FOR(j, 0, k){
            ll v, c;
            cin >> v >> c;
            dij.register_edge(i, v, c);
        }
    }

    dij.calc_shortest_path();
    FOR(i, 0, N){
        ll d = dij.distance(i);
        p2(i, d);
    }
    
    return 0;
}


Measured memory_bytes: 15668