#include <bits/stdc++.h> typedef long long LL; inline int rd() { int a = 1, b = 0; char c = getchar(); while (!isdigit(c)) a = c == '-' ? 0 : 1, c = getchar(); while (isdigit(c)) b = b * 10 + c - '0', c = getchar(); return a ? b : -b; } const int N = 1e5 + 233; int n, m; struct Graph { int to, nxt, cost; } g[N * 2]; int head[N], tot; inline void addedge(int x, int y, int c) { g[++tot].to = y, g[tot].nxt = head[x], g[tot].cost = c, head[x] = tot; } int fa[N], son[N], size[N], dep[N], dis[N]; int top[N], id[N], wh[N], wt[N], num; void dfs1(int x) { for (int i = head[x]; i; i = g[i].nxt) { int y = g[i].to; if (y != fa[x]) { fa[y] = x; dep[y] = dep[x] + 1; dis[y] = dis[x] + g[i].cost; size[y] = 1; dfs1(y); if (size[son[x]] < size[y]) son[x] = y; size[x] += size[y]; } } } void dfs2(int x, int topf) { top[x] = topf; id[x] = ++num; wh[num] = x; wt[num] = dis[x] - dis[fa[x]]; if (son[x]) { dfs2(son[x], topf); for (int i = head[x]; i; i = g[i].nxt) { int y = g[i].to; if (y != fa[x] && y != son[x]) dfs2(y, y); } } } #define ls(p) p << 1 #define rs(p) p << 1 | 1 int sz[N * 4], tag[N * 4]; LL edge[N * 4], sum[N * 4]; void build(int p, int L, int R) { if (L == R) { edge[p] = wt[L]; return; } int mid = (L + R) >> 1; build(ls(p), L, mid); build(rs(p), mid + 1, R); edge[p] = edge[ls(p)] + edge[rs(p)]; } inline void pushup(int p) { sz[p] = std::max(sz[ls(p)], sz[rs(p)]); sum[p] = sum[ls(p)] + sum[rs(p)]; } inline void pushdown(int p) { if (tag[p]) { sz[ls(p)] += tag[p]; sz[rs(p)] += tag[p]; tag[ls(p)] += tag[p]; tag[rs(p)] += tag[p]; sum[ls(p)] += (LL)tag[p] * edge[ls(p)]; sum[rs(p)] += (LL)tag[p] * edge[rs(p)]; tag[p] = 0; } } void add(int p, int l, int r, int v, int L, int R) { if (l <= L && r >= R) { sz[p] += v; tag[p] += v; sum[p] += (LL)v * edge[p]; return; } pushdown(p); int mid = (L + R) >> 1; if (l <= mid) add(ls(p), l, r, v, L, mid); if (r > mid) add(rs(p), l, r, v, mid + 1, R); pushup(p); } LL query(int p, int l, int r, int L, int R) { if (l <= L && r >= R) return sum[p]; pushdown(p); int mid = (L + R) >> 1; LL ret = 0; if (l <= mid) ret += query(ls(p), l, r, L, mid); if (r > mid) ret += query(rs(p), l, r, mid + 1, R); return ret; } inline int weight() { int p = 1, L = 1, R = n; while (L < R) { pushdown(p); int mid = (L + R) >> 1; if (sz[rs(p)] * 2 >= sz[1]) L = mid + 1, p = rs(p); else R = mid, p = ls(p); } return wh[L]; } inline void range_add(int x, int y) { while (top[x] != 1) { add(1, id[top[x]], id[x], y, 1, n); x = fa[top[x]]; } add(1, 1, id[x], y, 1, n); } inline LL range_query(int x) { LL ret = 0; while (top[x] != 1) { ret += query(1, id[top[x]], id[x], 1, n); x = fa[top[x]]; } return ret + query(1, 1, id[x], 1, n); } LL sum_dis_e, sum_e; inline LL getans(int x) { return sum_dis_e + dis[x] * sum_e - 2 * range_query(x); } int main() { n = rd(); m = rd(); for (int i = 1; i < n; ++i) { int x = rd(), y = rd(), c = rd(); addedge(x, y, c); addedge(y, x, c); } dfs1(1); dfs2(1, 1); build(1, 1, n); while (m--) { int x = rd(), y = rd(); sum_e += y; sum_dis_e += (LL)dis[x] * y; range_add(x, y); printf("%lld\n", getans(weight())); } return 0; }