/*
    最小公共祖先
    題意: 給出一顆無向有邊權樹, 詢問若干個(u,v)對的距離.


    所謂LCA 的Tarjan算法, 實際上就是在建樹的過程中把query中的lca給計算出來, 所以稱為`離線算法` . 是的, 本質就是這么簡單, 好多解釋都搞復雜了.

    步驟略, 自己google.
    理解這個算法一定要抓住`遞推`的思想(也有遞歸在里面, 也要抓住).
    Tarjan是利用并查集實現的, 在遞推過程中, 一棵樹的root節點代表這棵樹(聯系并查集來想), 這樣做的好處是, 如果問點i與j的lca, 我們只要找i,j都屬于的最小的哪棵子樹就行了, 因為該子樹就是我們的答案. 那如何確定是那顆子樹呢? 這一點后面再解釋一下.
    下面說Tarjan最巧妙的點了. 因為是在建樹的過程中計算所有query, 也就表示我們此刻是否能計算某一query對(u,v)的條件是 : u和v是否都已經遍歷過. 所以我們可以在遍歷到點v(假設經歷v的時間比u晚)的時候把query給計算出來. 比如lcm(u,v)就是find(u). 那此刻的find(v)和lcm(u,v)相不相等呢? 答案是不相等, 至少在我的代碼實現上不相等. 因為father[x]的更新是在`遞歸回去`的時候更新的, 而此刻在遍歷v點, 還沒遞歸回去呢, father[v]當然也就沒更新啦.
    其實上一段就已經回答了`如何確定哪棵子樹是我們想要的答案`這一問題了. 就是find(u)所代表的子樹! 注意, 是find(u), 不是find(v)! 因為u是在v之前已經被遍歷過了, 并且遞歸回去過sub_root過了, 也就是father[u]被更新為sub_root了, 所以find(u)可以代表當前的sub_tree, 即`最小包含(u,v)子樹`

下面兩個解釋, 推薦一下. 羅嗦一句, 看代碼更容易理解, 人腦模擬一遍更容易理解
    http://www.nocow.cn/index.php/Tarjan%E7%AE%97%E6%B3%95
    http://blog.chinaunix.net/uid-1721137-id-181005.html
*/
#include <vector>
#include <stdio.h>
using namespace std;
#define     MAXN    40001
#define     debug   printf("!\n")
vector<int> v[MAXN], w[MAXN], query[MAXN], ans_num[MAXN];
int father[MAXN], dis[MAXN], ans[201];
bool visit[MAXN];
int n;

void init()
{
    for(int i = 1; i <= n; i++) {
        v[i].clear();
        w[i].clear();
        ans_num[i].clear();
        query[i].clear();
        father[i] = i;
        dis[i] = 0;
        visit[i] = false;
    }
}

int find(int x) 
{ 
    return x == father[x] ? x : father[x] = find(father[x]); 
}
void Union(int x, int y) { father[find(y)] = find(x); }
void Tarjan(int now, int value)
{
    visit[now] = true;
    dis[now] = value;
    for(int Size = v[now].size(), i = 0; i < Size; i++) {
        int tmp = v[now][i];
        if(visit[tmp] != 0) continue;
        Tarjan(tmp, value + w[now][i]);
        Union(now, tmp);            //注意順序, 先Tarjan子節點tmp, 再更新其father[tmp], 因為要保證在遞推tmp所代表的子樹時, father[tmp] = tmp, 而與當前子樹無關. 遞歸回來的時候再把tmp代表的子樹`并入`到當前樹里
    }

    for(int Size = query[now].size(), i = 0; i < Size; i++) {
        int tmp = query[now][i];
        if(!visit[tmp]) continue;       //若visit[tmp] == true, 即表示tmp節點已經遍歷過, 此時可計算相應的query
        ans[ans_num[now][i]] = dis[now] + dis[tmp] - 2 * dis[find(tmp)];
    }
}

int main()
{
    int cases, Query, x, y, z;
    scanf("%d", &cases);
    while(cases--) {
        scanf("%d%d", &n, &Query);
        init();
        for(int i = 1; i < n; i++) {
            scanf("%d%d%d", &x, &y, &z);
            v[x].push_back(y);
            w[x].push_back(z);
            v[y].push_back(x);
            w[y].push_back(z);
        }

        for(int i = 0; i < Query; i++) {
            scanf("%d%d", &x, &y);
            query[x].push_back(y);
            query[y].push_back(x);
            ans_num[x].push_back(i);
            ans_num[y].push_back(i);
        }
        Tarjan(1, 0);
        for(int i = 0; i < Query; i++) printf("%d\n", ans[i]);
    }
    return 0;
}