// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define dd double
#define ld long double
#define sl(n) scanf("%lld", &n)
#define si(n) scanf("%d", &n)
#define sd(n) scanf("%lf", &n)
#define pll pair <ll, ll>
#define pii pair <int, int>
#define mp make_pair
#define pb push_back
#define all(v) v.begin(), v.end()
#define inf (1LL << 61)
#define loop(i, start, stop, inc) for(ll i = start; i <= stop; i += inc)
#define for1(i, stop) for(int i = 1; i <= stop; ++i)
#define for0(i, stop) for(int i = 0; i < stop; ++i)
#define rep1(i, start) for(int i = start; i >= 1; --i)
#define rep0(i, start) for(int i = (start-1); i >= 0; --i)
#define ms(n, i) memset(n, i, sizeof(n))
#define casep(n) printf("Case %lld:", ++n)
#define pn printf("\n")
#define pf printf
#define EL '\n'
#define fastio std::ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

// === Debug macro starts here ===
#ifndef ONLINE_JUDGE
#define DEBUG
#define SYS_COL system("COLOR")
#endif

int recur_depth = 0;
#ifdef DEBUG
#define dbg(x) {++recur_depth; auto x_=x; --recur_depth; SYS_COL; \
                cerr<<string(recur_depth, '\t')<<"\e[91m"<<__func__<<":" \
                <<__LINE__<<"\t"<<#x<<" = "<<x_<<"\e[39m"<<endl;}

template<typename Ostream, typename Cont>
typename enable_if<is_same<Ostream,ostream>::value,
            Ostream&>::type operator<<(Ostream& os,  const Cont& v) {
    os<<"[";
    for(auto& x:v){os<<x<<", ";}
    return os<<"]";
}
template<typename Ostream, typename ...Ts>
Ostream& operator<<(Ostream& os,  const pair<Ts...>& p){
    return os<<"{"<<p.first<<", "<<p.second<<"}";
}
#else
#define dbg(x)
#endif
// === Debug macro ends here ===

#define ff first
#define ss second

const int sz = 1e5 + 10, LN = 18, tsz = 31*sz+10;
int pre[sz], pa[LN][sz], depth[sz], roots[sz], start[sz], idn, tim;

struct Edge {
    int v, w;
};
vector <Edge> g[sz];

struct NODE
{
    int mx, nxt[2];
    void init()
    {
        nxt[0] = nxt[1] = -1;
    }
} trie[tsz];

void Insert(int u, int p, int val)
{
    roots[u] = ++idn;
    trie[ roots[u] ] = trie[ roots[p] ];
    int cur = roots[u];

    rep0(i, 30) {
        bool b = (val>>i) & 1;

        if(trie[cur].nxt[b] == -1) {
            trie[cur].nxt[b] = ++idn;
            trie[idn].init();
        }
        else {
            int tmp = ++idn;
            trie[tmp] = trie[ trie[cur].nxt[b] ];
            trie[cur].nxt[b] = tmp;

        }
        cur = trie[cur].nxt[b];
        trie[cur].mx = start[u];
    }
}

/// Finds maximum (X xor K)
int Search(int L, int U, int K)
{
    int ret = 0;
    int cur = roots[U];

    rep0(i, 30) {
        bool b = (K>>i) & 1, need = b^1;

        if(trie[cur].nxt[need] != -1 && trie[ trie[cur].nxt[need] ].mx >= start[L]) {
            ret = (ret<<1) | 1;
            cur = trie[cur].nxt[need];
        }
        else {
            ret <<= 1;
            cur = trie[cur].nxt[b];
        }
    }
    return ret;
}

void dfs(int u, int p, int c, int lev)
{
    pre[u] = c, pa[0][u] = p, depth[u] = lev, start[u] = ++tim;
    Insert(u, p, c);

    for(Edge &nd : g[u]) {
        if(nd.v == p)
            continue;

        dfs(nd.v, u, c^nd.w, lev+1);
    }
}

int LCA(int u, int v)
{
    if(depth[u] < depth[v]) swap(u,v);
    int diff = depth[u] - depth[v];

    for(int i = 0; i < LN; i++) if( (diff>>i)&1 ) u = pa[i][u];
    if(u == v) return u;

    for(int i = LN-1; i >= 0; i--) {
        if(pa[i][u] != pa[i][v]) {
            u = pa[i][u];
            v = pa[i][v];
        }
    }

    return pa[0][u];
}

int main()
{
    fastio;
    int t;
    cin >> t;

    while(t--) {
        int n, q;
        cin >> n >> q;

        for1(i, n-1) {
            int u, v, w;
            cin >> u >> v >> w;

            g[u].pb({v, w});
            g[v].pb({u, w});
        }

        roots[0] = idn = tim = 0;
        trie[ roots[0] ].init();
        ms(pa, 0);
        dfs(1, 0, 0, 0);

        for(int i=1; i<LN; i++)
            for(int j=1; j<=n; j++)
                if(pa[i-1][j] != 0)
                    pa[i][j] = pa[i-1][pa[i-1][j]];

        while(q--) {
            int u, v;
            cin >> u >> v;

            int lca = LCA(u, v);
            cout << max(Search(lca, u, pre[u]), Search(lca, v, pre[u])) << EL;
        }

        for1(i, n) g[i].clear();
    }

    return 0;
}