#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair <ll, ll> PII;
#define rep(i,n) for (ll i = 0; i < (ll)(n); i++)
const ll N = 100005;
ll n, m;
vector <ll> coor;
vector <PII> E[N];
ll fa[N][19];
ll dep[N];
struct Node {
	ll size;
	ll sum;
	Node *lc, *rc;
}pool[N * 20], *C, *root[N];

Node *newNode(Node *p = NULL) {
	if (p) {
		*C = *p;
	} else {
		C->size = C->sum = 0;
		C->lc = C->rc = NULL;
	}
	return C++;
}

Node *build(ll l, ll r) {
	Node *p = newNode();
	if (l + 1 < r) {
		ll mid = (l + r) / 2;
		p->lc = build(l, mid);
		p->rc = build(mid, r);
	}
	return p;
}

Node *ins(Node *p, ll i, ll cl = 0, ll cr = coor.size()) {
	Node *q = newNode(p);
	q->size++;
	q->sum += coor[i];
	if (cl + 1 == cr) return q;
	ll mid = (cl + cr) / 2;
	if (i < mid)
		q->lc = ins(p->lc, i, cl, mid);
	else
		q->rc = ins(p->rc, i, mid, cr);
	return q;
}

void bfs() {
	C = pool;
	static ll Q[N], vis[N];
	ll qh = 0, qt = 1;
	Q[0] = 0;
	fill(vis, vis + n, 0);
	vis[0] = 1;
	fa[0][0] = 0;
	root[0] = build(0, coor.size());
	dep[0] = 0;
	while (qh < qt) {
		ll u = Q[qh++];
		rep (i, E[u].size()) {
			ll v = E[u][i].first;
			ll w = lower_bound(coor.begin(), coor.end(), E[u][i].second) - coor.begin();
			if (!vis[v]) {
				Q[qt++] = v;
				vis[v] = 1;
				root[v] = ins(root[u], w);
				fa[v][0] = u;
				dep[v] = dep[u] + 1;
			}
		}
	}
	for (ll k = 1; k < 19; k++) rep (i, n) fa[i][k] = fa[fa[i][k - 1]][k - 1];
}

ll getLca(ll x, ll y) {
	if (dep[x] > dep[y]) swap(x, y);
	for (ll k = 18; dep[x] != dep[y] && k >= 0; k--)
		if (dep[fa[y][k]] >= dep[x])
			y = fa[y][k];
	if (x == y) return x;
	for (ll k = 18; k >= 0; k--) {
		if (fa[x][k] != fa[y][k]) {
			x = fa[x][k];
			y = fa[y][k];
		}
	}
	if (fa[x][0] != fa[y][0]) while (1);
	return fa[x][0];
}

ll getMin(Node *a, Node *b, Node *c, ll cl = 0, ll cr = coor.size()) {
	if (cl + 1 == cr) {
		return coor[cl];
	} else {
		ll mid = (cl + cr) / 2;
		if (a->lc->size + b->lc->size - 2 * c->lc->size > 0) {
			return getMin(a->lc, b->lc, c->lc, cl, mid);
		} else {
			return getMin(a->rc, b->rc, c->rc, mid, cr);
		}
	}
}

ll getAug(Node *a, Node *b, Node *c, ll lim, ll lsz = 0, ll lsum = 0, ll cl = 0, ll cr = coor.size()) {
	if (cl + 1 == cr) {
		ll sz = a->size + b->size - 2 * c->size + lsz;
		ll res = (lim - (lsz * coor[cl] - lsum)) / sz + (ll)(coor[cl]);
		if (lim - (lsz * coor[cl] - lsum) < 0) while (1);
		return res;
	} else {
		ll mid = (cl + cr) / 2;
		ll sz = a->lc->size + b->lc->size - 2 * c->lc->size;
		ll sum = a->lc->sum + b->lc->sum  - 2 * c->lc->sum;
		if ((ll)(sz + lsz) * coor[mid] - sum - lsum <= lim) {
			return getAug(a->rc, b->rc, c->rc, lim, lsz + sz, lsum + sum, mid, cr);
		} else {
			return getAug(a->lc, b->lc, c->lc, lim, lsz, lsum, cl, mid);
		}
	}
}

int main() {
#ifdef cwj
	freopen("in", "r", stdin);
#endif
	ll Tc;
	scanf("%I64d", &Tc);
	rep (ri, Tc) {
		printf("Case #%I64d:\n", ri + 1);
		scanf("%I64d%I64d", &n, &m);
		rep (i, n) E[i].clear();
		coor.clear();
		rep (i, n - 1) {
			ll u, v, w;
			scanf("%I64d%I64d%I64d", &u, &v, &w);
			u--; v--;
			E[u].push_back(PII(v, w));
			E[v].push_back(PII(u, w));
			coor.push_back(w);
		}
		sort(coor.begin(), coor.end());
		coor.resize(unique(coor.begin(), coor.end()) - coor.begin());
		bfs();
		rep (i, m) {
			ll x, y, s, a, b, lca;
			scanf("%I64d%I64d%I64d%I64d%I64d", &x, &y, &s, &a, &b);
			swap(a, b);
			x--; y--;
			lca = getLca(x, y);
			ll minv = getMin(root[x], root[y], root[lca]);
			if (b <= a) {
				cout << (ll)(minv) + s / b << "\n";
			} else {
				ll res0, res1;
				res0 = minv;
				if (s >= b) {
					res0++;
					if ((s - b) / a > 0) res0 += (s - b) / a;
				}
				res1 = getAug(root[x], root[y], root[lca], s / a);
				cout << max(res0, res1) << "\n";
			}
		}
	}
	return 0;
}