#include<bits/stdc++.h>

using namespace std ;
typedef long long ll ;
#define F first
#define S second
const int MX = 100010 , MXLOG = 30 ;
ll INF = 1e17 ;
vector< pair< int , ll > > adj[MX] ;
vector< int > cycle ;
int vis[MX] , f , clr , cyc_len , head[MX] , par[MX][32] , dep[MX] ;
ll cost[MX] , pref[MX] ;
stack< int > st ;
map< int , int > num ;
void init ()
{
    for( int i = 0 ; i < MX ; ++i )adj[i].clear() ;
    for( int i = 0 ; i < MX ; ++i )cost[i] = INF ;
    cycle.clear() ;
    num.clear() ;
    memset( head , 0 , sizeof head ) ;
    memset( par , -1 , sizeof par ) ;
    memset( pref , 0 , sizeof pref ) ;
    memset( dep , 0 , sizeof dep ) ;
    while( !st.empty() )st.pop() ;
    cyc_len = 0 ;
    f = 0 ;
    clr++ ;
}

void dfs( int nd , int p = -1 )
{
    if( f ) return ;
    vis[nd] = clr ;
    st.push(nd) ;
    for( auto it : adj[nd] )
    {
        if( it.first == p || f )continue ;
        if( vis[it.first] != clr )
            dfs( it.first , nd ) ;
        else
        {
            while( st.top() != it.first )
            {
                int x = st.top() ;
                st.pop() ;
                cycle.push_back( x ) ;
            }
            cycle.push_back( it.first ) ;
            f = 1;
            return ;
        }
    }
    if( f ) return ;
    st.pop() ;
}

void trav( int nd , int p , int hd , ll c = 0 , int d = 0 )
{
    dep[nd] = d ;
    vis[nd] = clr ;
    head[nd] = hd ;
    par[nd][0] = p ;
    cost[nd] = min( cost[nd] , c ) ;
    for( auto it : adj[nd] )
        if( it.first == p || num[it.first] || vis[it.first] == clr ) continue ;
        else
            trav( it.first , nd , hd , c+it.second , d+1 ) ;
}

int LCA(int u , int v)
{
    if(dep[u] < dep[v])
        swap(u,v) ;
    int dist = dep[u] - dep[v] ;
    while(dist > 0)
    {
        int raise_by = log2(dist);
        u = par[u][raise_by];
        dist -= (1<<raise_by) ;
    }

    if(u == v)
    {
        return u ;
    }
    for(int j = MXLOG ; j >= 0 ; --j)
    {
        if((par[u][j] != -1) && (par[u][j] != par[v][j]))
        {
            u = par[u][j] ;
            v = par[v][j] ;
        }
    }
    return par[u][0] ;
}

void calc( int nd , int d )
{
    num[nd] = d ;
    if( d == cycle.size() ){
        for( auto it : adj[nd] )
        if( cycle[0] == it.first )
            pref[d] = it.second ;
            return ;
    }
    for( auto it : adj[nd] )
        if( cycle[d] == it.first )
        {
            pref[d] = it.second ;
            calc( it.first , d+1 ) ;
        }
}
/*
2
7 6
1 2 2
1 3 5
2 3 1
2 4 1
2 5 1
3 6 1
3 7 1
1
9 10
1 2 3
1 3 4
2 6 1
2 7 7
3 4 2
3 5 1
5 8 6
5 9 3
7 6 10
*/

int main()
{
//    freopen("out.txt" , "r",stdin) ;
//    freopen("t.txt" , "w",stdout) ;
    ll c ;
    clr = 1 ;
    int a , b , n , t , q ;
    scanf("%d" , &t) ;
    while( t-- )
    {
        init() ;
        scanf("%d %d" , &n , &q) ;
        while( n-- )
        {
            scanf("%d %d %lld" , &a , &b , &c) ;
            adj[a].push_back({b,c}) ;
            adj[b].push_back({a,c}) ;
        }
        dfs(1) ;
        reverse( cycle.begin() , cycle.end() ) ;
        for( auto it : cycle )
            num[it] = ++cyc_len ;
        calc(cycle[0],1) ;

        for( int i = 1 ; i <= cyc_len ; ++i )
            pref[i]+=pref[i-1] ;

        for( auto it : cycle )
        {
            clr++ ;
            trav( it , -1 , it ) ;
        }
        for(int j = 1; (1<<j) < MX ; ++j)
            for(int i = 1 ; i < MX ; ++i)
                if(par[i][j-1] != -1)
                    par[i][j] = par[ par[i][j-1] ][j-1] ;

        while( q-- )
        {
            ll ans = 0 ;
            scanf("%d %d" , &a , &b) ;
            if( head[a] != head[b] )
            {
                ans = cost[a] + cost[b] ;
                b = num[ head[b] ] ;
                a = num[ head[a] ] ;
                if( a > b ) swap( a , b ) ;
                ll path_on_cyc = min( pref[ b - 1 ] - pref[ a - 1 ] , pref[cyc_len] - pref[ b - 1 ] +  pref[ a - 1 ]  ) ;
                ans+=path_on_cyc ;
            }
            else
            {
                int lca = LCA( a , b ) ;
                ans = cost[a] + cost[b] - 2ll*cost[lca] ;
            }
        printf("%lld\n",ans) ;
        }
    }
    return 0 ;
}