#include using namespace std; using ll = long long; template using Pa = pair; template using vec = vector; template using vvec = vector>; template class LazySegmentTree { private: int sz,height; vec data; vec lazy; const F op; const G homo; const H comp; const Monoid e; const OperatorMonoid Oe; public: LazySegmentTree(int n,const F op,const G homo,const H comp, const Monoid &e,const OperatorMonoid Oe) : op(op),homo(homo),comp(comp),e(e),Oe(Oe) { sz = 1; height = 0; while(sz<=n) sz <<= 1,height++; data.assign(2*sz,0); lazy.assign(2*sz,Oe); } void renew(int n){ sz = 1; height = 0; while(sz<=n) sz <<= 1,height++; fill(data.begin(),data.begin()+2*sz,0); fill(lazy.begin(),lazy.begin()+2*sz,Oe); } void set(int k,const Monoid &x) { data[k+sz] = x; } void build() { for(int k=sz-1;k>0;k--) { data[k] = op(data[2*k], data[2*k+1]); } } inline void propagate(int k) { if(lazy[k]!=Oe) { lazy[2*k] = comp(lazy[2*k], lazy[k]); lazy[2*k+1] = comp(lazy[2*k+1], lazy[k]); data[k] = reflect(k); lazy[k] = Oe; } } inline Monoid reflect(int k) { return lazy[k] == Oe? data[k]:homo(data[k],lazy[k]); } inline void recalc(int k) { while(k>>=1) data[k] = op(reflect(2*k), reflect(2*k+1)); } inline void thrust(int k) { for(int i=height;i>0;i--) propagate(k>>i); } void update(int a, int b, const OperatorMonoid &x) { thrust(a+=sz); thrust(b+=sz-1); for(int l=a,r=b+1;l>=1,r>>=1) { if(l&1) lazy[l] = comp(lazy[l],x),++l; if(r&1) --r, lazy[r] = comp(lazy[r],x); } recalc(a); recalc(b); } Monoid query(int a, int b) { thrust(a+=sz); thrust(b+=sz-1); Monoid L = e, R = e; for(int l=a, r=b+1;l>= 1,r>>=1) { if(l&1) L = op(L,reflect(l++)); if(r&1) R = op(reflect(--r),R); } return op(L,R); } Monoid operator[](const int &k) { return query(k,k+1); } }; struct edge{ int to,id; ll dist; edge(int to,ll dist=1,int id=1):to(to),id(id),dist(dist){}; }; class CentroidDecomposition{ public: int N; vvec g; vec size; vec used; CentroidDecomposition(int N,vvec tree): N(N),g(tree){ size = used = vec(N,0); } int calc_size(int cur,int par){ int c = 1; for(auto& x:g[cur]){ if(x.to==par || used[x.to]) continue; c += calc_size(x.to,cur); } return size[cur] = c; } //tは連結成分の大きさ //cur以下のうち、削除して残る最大の部分木の大きさを返す Pa search_centroid(int cur,int par,int cmp_size){ Pa res = {1e9,-1}; int s = 1,ma = 0; for(auto& x:g[cur]){ if(x.to==par || used[x.to]) continue; res = min(res,search_centroid(x.to,cur,cmp_size)); ma = max(ma,size[x.to]); s += size[x.to]; } //子と親の部分木の大きい方 ma = max(ma,cmp_size-s); res = min(res,{ma,cur}); return res; } void dfs(int cur,int par,ll d,vec& dlist){ dlist.push_back(d); for(auto& e:g[cur]) if(e.to!=par && !used[e.to]){ dfs(e.to,cur,d+e.dist,dlist); } } int build(int v){ calc_size(v,-1); int centroid = search_centroid(v,-1,size[v]).second; used[centroid] = true; return centroid; } void disable(int v){used[v] = true;} bool is_alive(int v){return !used[v];} }; int main(){ cin.tie(0); ios::sync_with_stdio(false); int N,M; cin >> N >> M; vvec g(N); for(int i=0;i> a >> b; a--; b--; g[a].push_back(b); g[b].push_back(a); } auto op = [](ll a,ll b){return max(a,b);}; auto func = [](ll a,ll b){return a+b;}; auto comp = func; LazySegmentTree seg(N,op,func,comp,-1,0); struct query{ int id,x,y; ll z; bool operator<(const query& R)const{ return id Q(N); for(int i=0;i> x >> y >> z; x--; Q[x].push_back({i,x,y,z}); } vec ans(M); CentroidDecomposition CD(N,g); vec dep(N); queue que; que.push(0); while(!que.empty()){ int c = CD.build(CD.build(que.front())); que.pop(); vec now; int len = 0; dep[c] = 0; for(auto& q:Q[c]) now.push_back(q); auto dfs = [&](auto&& self,int cur,int par,int d)->void{ dep[cur] = d; len = max(len,d); for(auto& q:Q[cur]) now.push_back(q); for(auto& e:g[cur]) if(CD.is_alive(e.to) && e.to!=par){ self(self,e.to,cur,d+1); } }; for(auto& x:g[c]) if(CD.is_alive(x.to)) dfs(dfs,x.to,c,1); sort(now.begin(),now.end()); for(auto& q:now){ ans[q.id] += seg[dep[q.x]]; if(dep[q.x]<=q.y) seg.update(0,min(len,q.y-dep[q.x])+1,q.z); } now.clear(); for(auto& e:g[c]) if(CD.is_alive(e.to)){ int len2 = 1; auto dfs = [&](auto&& self,int cur,int par,int d)->void{ dep[cur] = d; len2 = max(len2,d); for(auto& q:Q[cur]) now.push_back(q); for(auto& e:g[cur]) if(CD.is_alive(e.to) && e.to!=par){ self(self,e.to,cur,d+1); } }; dfs(dfs,e.to,c,1); seg.renew(min(10*len2+1,N)); sort(now.begin(),now.end()); for(auto& q:now){ ans[q.id] -= seg[dep[q.x]]; if(dep[q.x]<=q.y) seg.update(0,min(len2,q.y-dep[q.x])+1,q.z); } que.push(e.to); now.clear(); } seg.renew(min(10*len+1,N)); } for(auto& x:ans) cout << x << "\n"; }