#include using namespace std; using ll = long long; template using Pa = pair; template using vec = vector; template using vvec = vector>; struct edge{ int to,id; ll dist; edge(int to,ll dist=1,int id=1):to(to),id(id),dist(dist){}; }; template struct SparseTable { vector> st; vector lookup; SparseTable(){} SparseTable(const vector &v) { int b = 0; while((1<(1<>1]+1; } } inline T query(int l,int r) { int b = lookup[r-l]; return min(st[b][l],st[b][r-(1< idx,dep,vs; vec dist; vec> init; SparseTable> st; vvec g; int pos; void dfs(int cur,int par,int d){ idx[cur] = pos; vs[pos] = cur; dep[pos++] = d; dist[cur] = d; for(auto& e:g[cur]) if(e.to!=par){ dfs(e.to,cur,d+1); vs[pos] = cur; dep[pos++] = d; } } public: LCA(){}; LCA(int N,int root,vvec g):idx(N),dep(2*N),vs(2*N),init(2*N),g(g){ pos = 0; dist = vec(N); dfs(root,-1,0); for(int i=0;i<2*N;i++){ init[i] = {dep[i],vs[i]}; } st = SparseTable>(init); } int lca(int u,int v){ if(idx[u]>idx[v]) swap(u,v); return st.query(idx[u],idx[v]+1).second; } int vid(int v){return idx[v];} int idv(int i){return vs[i];} int depth(int i){return dep[i];} int d(int i){return dist[i];} }; constexpr int si = 512; int main(){ cin.tie(0); ios::sync_with_stdio(false); int N,Q; cin >> N >> Q; vvec g(N); for(int i=0;i> a >> b; a--; b--; g[a].push_back(b); g[b].push_back(a); } LCA lca(N,0,g); struct query{ int x,y; ll z; }; vec q(Q); for(int i=0;i> x >> y >> z; x--; q[i] = {x,y,z}; } vec ans(N); auto dist = [&](int a,int b){ return lca.d(a)+lca.d(b)-2*lca.d(lca.lca(a,b)); }; for(int _=0;_