#include #include #include using namespace std; using namespace atcoder; using mint = modint998244353; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000001 #define Inf64 4000000000000000001 struct HLD{ vector sz,parent,depth,root,pos; vector arr; HLD(vector> &E){ sz.resize(E.size(),1); parent.resize(E.size(),0); depth.resize(E.size(),0); root.resize(E.size(),0); pos.resize(E.size(),0); dfs(0,-1,E); dfs2(0,-1,E,0); } void dfs(int now,int p,vector> &E){ parent[now] = p; if(p==-1){ depth[now] = 0; } else{ depth[now] = depth[p]+1; } for(int i=0;i> &E,int r){ pos[now] = arr.size(); arr.push_back(now); root[now] = r; int maxi = 0; int ind = -1; for(int i=0;i> query(int u,int v){ vector> ret; int t = 0; while(root[u]!=root[v]){ if(depth[root[u]] <= depth[root[v]]){ ret.insert(ret.begin()+t,{pos[root[v]], pos[v]}); v = parent[root[v]]; } else{ ret.insert(ret.begin()+t,{pos[u],pos[root[u]]}); u = parent[root[u]]; t++; } } ret.insert(ret.begin()+t,{pos[u],pos[v]}); return ret; } int lca(int u,int v){ for(;;v=parent[root[v]]){ if(pos[u]>pos[v])swap(u,v); if(root[u]==root[v])return u; } } int get_distance(int u,int v){ return depth[u] + depth[v] - 2 * depth[lca(u,v)]; } }; vector> t; void dfs(int cv,int pv,auto &E){ //cout< op(array a,array b){ array ret; rep(i,3)ret[i]= min(a[i],b[i]); return ret; } array e(){ array ret; rep(i,3)ret[i] = Inf64; return ret; } array mapping(array a,array b){ rep(i,3)a[i] += b[i]; return a; } array composition(array a,array b){ return mapping(a,b); } array id(){ array ret; rep(i,3)ret[i] = 0; return ret; } bool F(array a){ return a[2]>0; } int main(){ int n,q; cin>>n>>q; vector>> E(n); vector> es(n); rep(i,n-1){ long long a,b,c; cin>>a>>b>>c; a--,b--; E[a].emplace_back(b,c); E[b].emplace_back(a,c); es[a].push_back(b); es[b].push_back(a); } t.resize(n); dfs(0,-1,E); //cout<<'a'<> ta(n); rep(i,n){ ta[H.pos[i]] = t[i]; } swap(ta,t); } lazy_segtree,op,e,array,mapping,composition,id> seg(t); //cout<<'b'<>type; if(type==1){ int v; long long x; cin>>v>>x; v--; auto ret = H.query(v,0); array tt; tt[0] = 0; tt[1] = x; tt[2] = -x; rep(i,ret.size()){ int ll = ret[i].first,rr = ret[i].second; if(ll>rr)swap(ll,rr); rr++; seg.apply(ll,rr,tt); } if(seg.all_prod()[2]<=0){ int target; rep(i,ret.size()){ int ll = ret[i].first,rr = ret[i].second; if(ll>rr)swap(ll,rr); rr++; if(seg.prod(ll,rr)[2]>0)continue; ll = ret[i].first,rr = ret[i].second; if(ll(ll); target = H.arr[tr]; break; } else{ swap(ll,rr); rr++; int tl = seg.min_left(rr); target = H.arr[tl-1]; break; } break; } //cout<rr)swap(ll,rr); rr++; seg.apply(ll,rr,tt); } seg.set(H.pos[target],e()); } } else{ cout<