Ishank lives in a country in which there are N$N$ cities and N−1$N-1$ roads. All the cities are connected via these roads. Each city has been assigned a unique number from 1 to N$N$. The country can be assumed as a tree, with nodes representing the cities and edges representing the roads. The tree is rooted at 1.Every Time, when a traveler through a road, he will either gain some amount or has to pay some amount.
Abhineet is a traveler and wishes to travel to various cities in this country. There's a law in the country for travelers, according to which, when a traveler moves from the city A$A$ to city B$B$, where city A$A$ and B$B$ are connected by a road then the traveler is either paid or has to pay the amount of money equal to profit or loss respectively. When he moves from A$A$ to B$B$, he hires a special kind of vehicle which can reverse its direction at most once. Reversing the direction means earlier the vehicle is going towards the root, then away from the root or vice versa. Abhineet is analyzing his trip and therefore gave Q$Q$ queries to his friend, Ishank, a great coder. In every query, he gives two cities A$A$ and B$B$. Ishank has to calculate the maximum amount he can gain (if he cannot gain, then the minimum amount he will lose) if he goes from the city A$A$ to city B$B$.

-----Input:-----
-The first line of the input contains a two space-separated integers N and Q.
-The next N-1 line contains 3 space-separated integers Xi and Yi and Zi denoting that cities Xi and Yi are connected by a road which gives profit Zi (Negative Zi represents loss).
-The next Q contains 2 space-separated integers A and B denoting two cities.

-----Output:-----
Print a single line corresponding to each query — the maximum amount he can gain (if he cannot gain, then the minimum amount he will lose with negative sign) if he goes from city A to city B.

-----Constraints-----
- 2≤N≤105$2 \leq N \leq 10^5$
- 1≤Q≤105$1 \leq Q \leq 10^5$
- 1≤Xi,Yi,A,B≤N$1 \leq Xi, Yi, A, B \leq N$
- abs(Zi)≤109$ abs(Zi) \leq 10^9$

-----Sample Input:-----
9 5
1 2 8
1 3 -9
2 4 1
2 5 -6
3 6 7
3 7 6
6 8 3
6 9 4
1 2
2 7
4 3
3 2
8 9

-----Sample Output:-----
10
5
0
-1
21

-----EXPLANATION:-----
In the first query, he goes from 1 to 2, 2 to 4, takes a turn and go to 2. Therefore profit=8+1+1=10.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'try:\n    X=list(map(int, input().split()))\nexcept:\n    X=[0,0]\nch=[]\nchnew=[]\npar={}\npar[1]=0\nfor i in range(X[0]+1):\n    ch.append([])\n    chnew.append([])\nfor i in range(X[0]-1):\n    Y=list(map(int, input().split()))\n    #par[Y[1]]=[Y[0],Y[2]]\n    ch[Y[0]].append([Y[1],Y[2]])\n    ch[Y[1]].append([Y[0],Y[2]])\ntre=[1]\nwhile(len(tre)):\n    cr=tre[-1]\n    tre=tre[:-1]\n    for i in ch[cr]:\n        chnew[cr].append(i)\n        par[i[0]]=[cr,i[1]]\n        tre.append(i[0])\n        for j in ch[i[0]]:\n            if(j[0]==cr):\n                ch[i[0]].remove(j)\n                break\nch=chnew\ndef goup(par,nd):\n    if(nd==1):\n        return 0\n    else:\n        p=par[nd]\n        ans=p[1]+goup(par,p[0])\n        return (max([ans,0]))\n\ndef godown(ch,nd):\n    ans=0\n    for i in ch[nd]:\n        ans=max([(i[1]+godown(ch,i[0])),ans])\n    return(ans)\n\nfor i in range(X[1]):\n    Z=list(map(int,input().split()))\n    r=Z[0]\n    s=Z[1]\n    nans=0\n    while(r!=s):\n        if(r>s):\n            nans=nans+par[r][1]\n            r=par[r][0]\n        else:\n            nans=nans+par[s][1]\n            s=par[s][0]\n    if((r==Z[0]) or (r==Z[1])):\n        if(Z[0]<Z[1]):\n            nans=nans+2*max(goup(par,Z[0]),godown(ch,Z[1]))\n        else:\n            nans=nans+2*max(goup(par,Z[1]),godown(ch,Z[0]))\n    else:\n        nans=nans+2*goup(par,r)\n    print(nans)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 14443