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


// Util
#define MAX(x, y) ((x) >= (y) ? (x) : (y))
//


// 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, buf_cap(buf) << 2);
    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) for(size_t i = pq_len(q); i > 1 && cmp((q)+i, (q)+i/2) == 1; i /= 2)swap((q)+i, (q)+i/2)
#define pq__down(q) 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);}

#define pq_push(q, ...) (pq__fit((q), 1 + pq_len(q)), (q)[++pq__hdr(q)->len] = (__VA_ARGS__));pq__up(q)
#define pq_pop(q) (q)[1]; (q)[1] = (q)[pq__hdr(q)->len--]; pq__down(q)
#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(2, pq_cap(Q) << 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;
}
//


// Node
typedef struct PII {
    int f, s;
} PII;

void swap(PII *x, PII *y) {
    PII tmp = *y;
    *y = *x, *x = tmp;
}

int cmp(PII *l, PII *r) {
    if(l->f < r->f) return -1;
    if(l->f > r->f) return 1;
    return 0;
}
//


// Solve
#define add_edge(E, u, v, w) (buf_push(E[u], (PII){v, w}))

int dijkstra(PII **E, int *d, int N, int s) {
    PII *Q = NULL;
    for(int i = 0; i < N; ++i) d[i] = 1 << 28;

    pq_push(Q, (PII){d[s] = 0, s});
    while(pq_len(Q)) {
        PII e = pq_pop(Q);

        if(e.f > d[e.s]) continue;

        for(PII *p = E[e.s]; p != E[e.s] + buf_len(E[e.s]); ++p) {
            int x = p->f, y = p->s + e.f;
            if(y < d[x]) d[x] = y;
            pq_push(Q, (PII){y, x});
        }
    }
}

int main(int argc, char **argv) {
    int n = get_uint();
    PII *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: 10800