#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const LL LINF = 1e18;

struct Node
{
	int col[2];
	LL d[2];
	
	Node() 
	{
		col[0] = -1;
		col[1] = -1;
		d[0] = -LINF;
		d[1] = -LINF;
	}
};

struct Segtree
{
	int n;
	vector<Node> t;
	
	void init(int _n)
	{
		n = 1;
		while (n < _n) n *= 2;
		t.assign(2 * n - 1, Node());
	}
	
	Node combine(Node n1, Node n2)
	{
		Node res;
		int i = 0;
		int j = 0;
		FOR (it, 0, 2)
		{
			if (n1.d[i] > n2.d[j])
				res.col[it] = n1.col[i], res.d[it] = n1.d[i];
			else
				res.col[it] = n2.col[j], res.d[it] = n2.d[j];
			if (res.col[it] == n1.col[i])
				i++;
			if (res.col[it] == n2.col[j])
				j++;
		}
		return res;
	}
	Node query(int v, int tl, int tr, int l, int r)
	{
		if (l <= tl && tr <= r)
			return t[v];
		if (r <= tl || tr <= l)
			return Node();
		int tm = (tl + tr) / 2;
		return combine(query(2 * v + 1, tl, tm, l, r),
					   query(2 * v + 2, tm, tr, l, r));
	}
	Node query(int l, int r)
	{
		return query(0, 0, n, l, r);
	}
	
	void upd(int v, int tl, int tr, int i, int c, LL d)
	{
		if (tl + 1 == tr)
		{
			t[v].col[0] = c;
			t[v].d[0] = d;
			return;
		}
		int tm = (tl + tr) / 2;
		if (i < tm)
			upd(2 * v + 1, tl, tm, i, c, d);
		else
			upd(2 * v + 2, tm, tr, i, c, d);
		t[v] = combine(t[2 * v + 1], t[2 * v + 2]);
	}
	void upd(int i, int c, LL d)
	{
		upd(0, 0, n, i, c, d);
	}
};


const int N = 500'447;

vector<PII> g[N];
int sz[N];
int par[N]; //parent in centroid tree
bool usedC[N];

int dfsSZ(int v, int pr)
{
	sz[v] = 1;
	for (auto [to, _] : g[v])
	{
		if (to != pr && !usedC[to])
			sz[v] += dfsSZ(to, v);
	}
	return sz[v];
}

void build(int u, int p = -1)
{
	dfsSZ(u, -1);
	int szAll = sz[u];
	int pr = u;
	while (true)
	{
		int v = -1;
		for (auto [to, _] : g[u])
		{
			if (to == pr || usedC[to])
				continue;
			if (sz[to] * 2 > szAll)
			{
				v = to;
				break;
			}
		}
		if (v == -1)
			break;
		pr = u;
		u = v;
	}
	
	int cent = u;
	par[cent] = p;
	usedC[cent] = true;
	
	for (auto [to, _] : g[cent])
	{
		if (!usedC[to])
		{
			build(to, cent);
		}
	}
}

const int LOG = 20;
int up[LOG][N];
LL dis[N];
int tin[N];
int tout[N];
int T = 0;

void dfs1(int v, int p = 0, LL ds = 0)
{
	tin[v] = T++;
	up[0][v] = p;
	dis[v] = ds;
	FOR (i, 1, LOG)
		up[i][v] = up[i - 1][up[i - 1][v]];
	for (auto [to, w] : g[v])
	{
		if (to != p)
			dfs1(to, v, ds + w);
	}
	tout[v] = T++;
}

bool is_parent(int p, int v)
{
	return tin[p] <= tin[v] && tout[v] <= tout[p];
}
int lca(int u, int v)
{
	if (is_parent(u, v))
		return u;
	RFOR (i, LOG, 0)
	{
		int nu = up[i][u];
		if (!is_parent(nu, v))
			u = nu;
	}
	return up[0][u];
}

LL f(int u, int v)
{
	return dis[u] + dis[v] - 2 * dis[lca(u, v)];
}

vector<tuple<int, int, int, LL>> a[N];
Segtree st[N];
int col[N];

void add(int v, int c)
{
	int u = v;
	int to = -1;
	while (v != -1)
	{
		tuple<int, int, int, LL> tpl = {to, u, c, f(u, v)};
		a[v].PB(tpl);
		to = v;
		v = par[v];
	}
}

void recalc(int& A, int& B, int v)
{
	LL dAB = f(A, B);
	if (f(A, v) > dAB)
		B = v;
	else if(f(B, v) > dAB)
		A = v;
}

void color(int v, int c)
{
	int u = v;
	int to = -1;
	while (v != -1)
	{
		LL distUV = f(u, v);
		tuple<int, int, int, LL> tpl = {to, u, col[u], distUV};
		int idx = lower_bound(ALL(a[v]), tpl) - a[v].begin();	
		if (a[v][idx] == tpl)
			st[v].upd(idx, -1, -LINF);
		get<2>(tpl) = c;
		idx = lower_bound(ALL(a[v]), tpl) - a[v].begin();
		st[v].upd(idx, c, distUV);
		to = v;
		v = par[v];
	}	
	col[u] = c;
}

LL F(int v)
{
	int u = v;
	int to = -1;
	LL ans = 0;
	while (v != -1)
	{
		int l = lower_bound(ALL(a[v]), make_tuple(to, -1, 0, 0)) - a[v].begin();
		int r = upper_bound(ALL(a[v]), make_tuple(to, N, 0, 0)) - a[v].begin();
		Node n1 = st[v].query(0, l);
		Node n2 = st[v].query(r, SZ(a[v]));
		Node res = st[v].combine(n1, n2);
		if (res.col[0] != col[u])
			ans = max(ans, res.d[0]);
		else if (res.col[1] != col[u])
			ans = max(ans, res.d[1]);
		to = v;
		v = par[v];
	}
	return ans;
}

void solve()
{
	int q, C;
	cin >> q >> C;
	col[0] = C;
	int n = 1;
	vector<tuple<int, int, int>> queries(q);
	FOR (i, 0, q)
	{
		int t;
		cin >> t;
		if (t == 0)
		{
			int x, c, d;
			cin >> x >> c >> d;
			x--;
			g[x].PB({n, d});
			g[n++].PB({x, d});
			queries[i] = {t, x, c};
		}
		else
		{
			int x, c;
			cin >> x >> c;
			x--;
			queries[i] = {t, x, c};
		}
	}
	FOR (i, 1, n)
		col[i] = -1;
	build(0);
	dfs1(0);
	
	FOR (i, 0, q)
		add(get<1>(queries[i]), get<2>(queries[i]));
	
	FOR (i, 0, n)
	{
		sort(ALL(a[i]));
		st[i].init(SZ(a[i]));
	}
	
	int A = 0, B = 0;
	FOR (i, 0, q)
	{
		auto [t, v, c] = queries[i];
		
		if (t == 0)
			recalc(A, B, v);
		
		color(v, c);
		
		cout << max(F(A), F(B)) << '\n';		
	}
	
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	
	return 0;
}