#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define sz(x) (int) (x).size()
#define i64 int64_t
#define all(x) (x).begin(), (x).end()

const int BUF_SZ = 1 << 15;
const int LG = 20;
const int FAKE = 5e5 + 3;
const int mxn = 5e5 + 5;
const int MM = 10;

inline int log2_floor(unsigned long long i) {
    return i ? 63 - __builtin_clzll(i) : -1;
}

inline namespace Input {
    char buf[BUF_SZ]; int pos; int len;
    inline char next_char() {
        if (pos == len) {
            pos = 0;
            len = (int)fread(buf, 1, BUF_SZ, stdin);
            if (!len) { return EOF; }
        }
        return buf[pos++];
    }
    inline i64 read_int() {
        i64 x; char ch; int sgn = 1;
        while (!isdigit(ch = next_char())) {
            if (ch == '-') { sgn *= -1; }
        }
        x = ch - '0';
        while (isdigit(ch = next_char())) { x = x * 10ll + (ch - '0'); }
        return x * sgn;
    }
}

inline namespace Output {
    char buf[BUF_SZ]; int pos;
    inline void flush_out() { fwrite(buf, 1, pos, stdout); pos = 0; }
    inline void write_char(char c) {
        if (pos == BUF_SZ) { flush_out(); }
        buf[pos++] = c;
    }
    inline void write_int(i64 x) {
        static char num_buf[100];
        if (x < 0) { write_char('-'); x *= -1; }
        int len = 0;
        do {
            num_buf[len++] = (char)('0' + (x % 10));
            x /= 10;
        } while (x);
        while (len) { write_char(num_buf[--len]); }
        write_char('\n');
    }
    void init_output() { assert(atexit(flush_out) == 0); }
}

vector<array<int,2>> adj[FAKE];
int etour[4*FAKE], tin[FAKE], tot[FAKE];
i64 dtour[4*FAKE], dep[FAKE];
int tourp = 0;

void tinit(int n) {
    for (int i = 0; i < n; i++) {
        adj[i].clear();
    }
    tourp = 0;
}

void add_edge(int u, int v, i64 w) {
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
}

void dfs(int v, int p, i64 d) {
    dep[v] = d;
    tin[v] = tourp;
    etour[tourp++] = v;
    for (const auto& e : adj[v]) {
        if (e[0] == p) continue;
        dfs(e[0], v, d + e[1]);
        etour[tourp++] = v;
    }
    tot[v] = tourp;
    etour[tourp++] = v;
}

int sparsetable[LG][4*FAKE];
void init_sparse() {
    dfs(0, 0, 0);
    for (int i = 0; i < tourp; i++) {
        dtour[i] = dep[etour[i]];
        sparsetable[0][i] = i;
    }
    for (int i = 1; i < LG; i++) {
        for (int j = 0; j + (1 << i) <= tourp; j++) {
            sparsetable[i][j] = (dtour[sparsetable[i-1][j]] < dtour[sparsetable[i-1][j + (1 << (i-1))]] ? sparsetable[i-1][j] : sparsetable[i-1][j + (1 << (i-1))]);
        }
    }
}

int rmq(int l, int r) {
    int i = log2_floor(r - l + 1);
    return (dtour[sparsetable[i][l]] < dtour[sparsetable[i][r - (1 << i) + 1]] ? sparsetable[i][l] : sparsetable[i][r - (1 << i) + 1]);
}

int lca(int u, int v) {
    return etour[rmq(min(tin[u], tin[v]), max(tot[u], tot[v]))];
}

i64 dist(int u, int v) {
    return (u == FAKE || v == FAKE) ? -69 : dep[u] + dep[v] - 2 * dep[lca(u, v)];
}

int n, q, c[mxn], qr[mxn][4], np;
vector<int> col[mxn];

void chmax(int &x, int &y, int x1, int y1) {
    if (dist(x1, y1) >= dist(x, y)) {
        x = x1;
        y = y1;
    }
}

int lo[MM*mxn], hi[MM*mxn], x[MM*mxn], y[MM*mxn], xd[MM*mxn], yd[MM*mxn], CXD[MM*mxn];
int lc[MM*mxn], rc[MM*mxn];
int nx = 0;

inline int create_node(int cxd) {
    CXD[nx] = cxd;
    x[nx] = y[nx] = FAKE;
    lc[nx] = rc[nx] = -1;
    return nx++;
}

int create_node(int l, int h, int cxd) {
    lo[nx] = l;
    hi[nx] = h;
    return create_node(cxd);
}

void pull(int v) {
    if (lc[v] != -1 && x[lc[v]] == FAKE) lc[v] = -1;
    if (rc[v] != -1 && x[rc[v]] == FAKE) rc[v] = -1;
    x[v] = y[v] = xd[v] = yd[v] = FAKE;
    if (lc[v] == -1 && rc[v] == -1) return;
    if (rc[v] == -1) {
        x[v] = x[lc[v]];
        y[v] = y[lc[v]];
        if (CXD[v]) {
            xd[v] = xd[lc[v]];
            yd[v] = yd[lc[v]];
        }
        return;
    }
    if (lc[v] == -1) {
        x[v] = x[rc[v]];
        y[v] = y[rc[v]];
        if (CXD[v]) {
            xd[v] = xd[rc[v]];
            yd[v] = yd[rc[v]];
        }
        return;
    }
    if (CXD[v]) {
        int lx = x[lc[v]], rx = x[rc[v]], ly = y[lc[v]], ry = y[rc[v]];
        int lxd = xd[lc[v]], rxd = xd[rc[v]], lyd = yd[lc[v]], ryd = yd[rc[v]];
        chmax(xd[v], yd[v], lx, rx);
        chmax(xd[v], yd[v], lx, ry);
        chmax(xd[v], yd[v], ly, rx);
        chmax(xd[v], yd[v], ly, ry);
        chmax(xd[v], yd[v], lxd, lyd);
        chmax(xd[v], yd[v], rxd, ryd);
        x[v] = xd[v];
        y[v] = yd[v];
        if (c[lx] != c[ly]) chmax(xd[v], yd[v], lx, ly);
        chmax(x[v], y[v], lx, ly);
        chmax(x[v], y[v], rx, ry);
    } else {
        int lx = x[lc[v]], rx = x[rc[v]], ly = y[lc[v]], ry = y[rc[v]];
        chmax(x[v], y[v], lx, ly);
        chmax(x[v], y[v], lx, rx);
        chmax(x[v], y[v], lx, ry);
        chmax(x[v], y[v], ly, rx);
        chmax(x[v], y[v], ly, ry);
        chmax(x[v], y[v], rx, ry);
    }
}

void point_set(int v, int I, int X, int Y) {
    if (lo[v] == I && hi[v] == I) {
        x[v] = X;
        y[v] = Y;
        xd[v] = yd[v] = FAKE;
        return;
    }
    if (I <= (lo[v] + hi[v]) / 2) {
        if (lc[v] == -1) lc[v] = create_node(lo[v], (lo[v] + hi[v]) / 2, CXD[v]);
        point_set(lc[v], I, X, Y);
    } else {
        if (rc[v] == -1) rc[v] = create_node((lo[v] + hi[v]) / 2 + 1, hi[v], CXD[v]);
        point_set(rc[v], I, X, Y);
    }
    pull(v);
}

int crt[mxn], trt;

void solve() {
    nx = 0;
    for (int i = 0; i <= q; i++) col[i].clear();
    q = read_int();
    c[0] = read_int();
    n = 0;
    col[c[0]].push_back(0);
    tinit(q + 1);
    np = 1;
    for (int i = 0; i < q; i++) {
        qr[i][0] = read_int();
        qr[i][1] = read_int();
        qr[i][2] = read_int();
        if (!qr[i][0]) {
            i64 d = read_int();
            add_edge(qr[i][1] - 1, np++, d);
            n++;
            qr[i][1] = np;
        }
        qr[i][1]--;
        col[qr[i][2]].push_back(qr[i][1]);
    }
    for (int i = 0; i <= q; i++) {
        sort(all(col[i]));
        col[i].erase(unique(all(col[i])), col[i].end());
    }
    init_sparse();
    for (int i = 0; i <= q; i++) {
        crt[i] = create_node(0, sz(col[i]) + 1, 0);
    }
    trt = create_node(0, q + 1, 1);
    point_set(crt[c[0]], 0, 0, 0);
    point_set(trt, c[0], x[crt[c[0]]], y[crt[c[0]]]);
    for (int i = 0; i < q; i++) {
        int tr = qr[i][0], xx = qr[i][1], ci = qr[i][2];
        int pcx = c[xx];
        c[xx] = ci;
        if (tr) {
            int xtv = lower_bound(all(col[pcx]), xx) - col[pcx].begin();
            point_set(crt[pcx], xtv, FAKE, FAKE);
            point_set(trt, pcx, x[crt[pcx]], y[crt[pcx]]);
        }
        int xtv = lower_bound(all(col[ci]), xx) - col[ci].begin();
        point_set(crt[ci], xtv, xx, xx);
        point_set(trt, ci, x[crt[ci]], y[crt[ci]]);
        write_int(max(dist(xd[trt], yd[trt]), 0ll));
    }
}

signed main() {
    init_output();
    int t = read_int();;
    while (t--) {
        solve();
    }
    return 0;
}
//