#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

// util
#define MAX(x, y) ((x) >= (y) ? (x) : (y))
void swap(void *x, void *y, size_t size) {
    void *tmp = malloc(size);
    memcpy(tmp, x, size);
    memcpy(x, y, size);
    memcpy(y, tmp, size);
    free(tmp);
}

// fast I/O
int get_uint() {
    int n = 0;
    int c = getchar_unlocked();
    if(c < 48 || 57 < c) return c;
    while(47 < c && c < 58) n = 10 * n + (c & 0xf), c = getchar_unlocked();
    return n;
}
void put_uint(int n) {
    if(!n) {
        putchar_unlocked('0');
        return;
    }
    char buf[11];
    int i = 0;
    while(n) buf[i++] = (char)(n % 10 + '0'), n /= 10;
    while(i--)putchar_unlocked(buf[i]);
}

// stretchy buffer(vector)
typedef struct BufHdr {
    size_t len;
    size_t cap;
    char buf[0];
} BufHdr;
#define buf__hdr(b) ((BufHdr *)((char *)(b) - offsetof(BufHdr, buf)))
#define buf__fits(b, n) (buf_len(b) + (n) <= buf_cap(b))
#define buf__fit(b, n) (buf__fits(b, n) ? 0 : ((b) = buf__grow(b, buf_len(b) + (n), sizeof(*(b)))))
#define buf_len(b) ((b) ? buf__hdr(b)->len : 0)
#define buf_cap(b) ((b) ? buf__hdr(b)->cap : 0)
#define buf_push(b, ...) (buf__fit(b, 1), (b)[buf_len(b)] = (__VA_ARGS__), buf__hdr(b)->len++)
#define buf_free(b) ((b) ? free(buf__hdr(b)) : 0)
void *buf__grow(const void *buf, size_t new_len, size_t elem_size) {
    size_t new_cap = MAX(1 + 2 * buf_cap(buf), new_len);
    size_t new_size = offsetof(BufHdr, buf) + new_cap * elem_size;
    BufHdr *new_hdr;
    if(buf) {
        new_hdr = realloc(buf__hdr(buf), new_size);
    } else {
        new_hdr = malloc(new_size);
        new_hdr->len = 0;
    }
    new_hdr->cap = new_cap;
    return new_hdr->buf;
}

// priority queue
typedef struct PQueue {
    size_t len;
    size_t cap;
    char heap[];
} PQueue;
#define pq__hdr(q) ((PQueue *)((char *)(q) - offsetof(PQueue, heap)))
#define pq__fit(q, n) ((n) <= pq_cap(q) ? 0 : ((q) = pq__grow((q), (n), sizeof(*(q)))))
#define pq__up(q, cmp) for(size_t i = pq_len(q); i > 1 && cmp((q)+i, (q)+i/2) == 1; i /= 2)swap((q)+i, (q)+i/2, sizeof(q))
#define pq__down(q, cmp) for(int i = 1, dt = -1; i != dt; i = dt){const size_t N = pq_len(q); int left = i*2, right = i*2 + 1; dt=i; if(left<=N && cmp((q)+left,(q)+dt))dt=left; if(right<=N && cmp((q)+right,(q)+dt))dt=right; swap((q)+i, (q)+dt, sizeof(q));}
#define pq_push(q, cmp, ...) (pq__fit((q), 1 + pq_len(q)), (q)[++pq__hdr(q)->len] = (__VA_ARGS__));pq__up(q, cmp)
#define pq_pop(q, cmp) (q)[1]; (q)[1] = (q)[pq__hdr(q)->len--]; pq__down(q, cmp)
#define pq_cap(q) ((q) ? pq__hdr(q)->cap : 0)
#define pq_len(q) ((q) ? pq__hdr(q)->len : 0)
void *pq__grow(const void *Q, size_t new_len, size_t elem_size) {
    size_t new_cap = MAX(pq_cap(Q) * 2, 2);
    size_t new_size = offsetof(PQueue, heap) + new_cap * elem_size;
    PQueue *new_hdr;
    if(Q) new_hdr = realloc(pq__hdr(Q), new_size);
    else new_hdr = malloc(new_size), new_hdr->len = 0;
    new_hdr->cap = new_cap;
    return new_hdr->heap;
}

typedef struct Edge {
    int cost, to;
} Edge;
#define cmp_edge(l, r) ((l)->cost < (r)->cost ? -1 : (l)->cost > (r)->cost ? 1 : 0)
#define add_edge(E, u, v, c) (buf_push(E[u], (Edge){v, c}))
int dijkstra(Edge **E, int *d, int N, int s) {
    Edge *Q = NULL;
    for(int i = 0; i < N; ++i) d[i] = 1 << 28;
    pq_push(Q, cmp_edge, (Edge){d[s] = 0, s});
    while(pq_len(Q)) {
        Edge e = pq_pop(Q, cmp_edge);
        if(e.cost > d[e.to]) continue;
        for(Edge *p = E[e.to]; p != E[e.to] + buf_len(E[e.to]); ++p) {
            int x = p->cost, y = p->to + e.cost;
            if(y < d[x]) d[x] = y;
            pq_push(Q, cmp_edge, (Edge){y, x});
        }
    }
}

int main(int argc, char **argv) {
    int n = get_uint();
    Edge *E[n];
    for(int i = 0; i < n; ++i) E[i] = NULL;
    for(int i = 0; i < n; ++i) {
        int u = get_uint();
        int k = get_uint();
        for(int j = 0; j < k; ++j) add_edge(E, u, get_uint(), get_uint());
    }
    int d[n];
    dijkstra(E, d, n, 0);
    for(int i = 0; i < n; ++i) {
        put_uint(i), putchar_unlocked(' ');
        put_uint(d[i]), putchar_unlocked('\n');
    }
    return 0;
}



Measured memory_bytes: 7912