Problem: A group of researchers are studying fish population in a natural system of lakes and rivers. The system contains n lakes connected by n - 1 rivers. Each river has integer length (in kilometers) and can be traversed in both directions. It is possible to travel between any pair of lakes by traversing the rivers (that is, the network of lakes and rivers form a tree).

There is an unknown number of indistinguishable fish living in the lakes. On day 1, fish can be at arbitrary lakes. Fish can travel between lakes by swimming the rivers. Each fish can swim a river l kilometers long in any direction in l days. Further, each fish can stay any number of days in any particular lake it visits. No fish ever appear or disappear from the lake system. Each lake can accomodate any number of fish at any time.

The researchers made several observations. The j-th of these observations is "on day d_j there were at least f_j distinct fish in the lake p_j". Help the researchers in determining the smallest possible total number of fish living in the lake system that doesn't contradict the observations.

Input

The first line contains a single integer n (1 ≤ n ≤ 10^5) — the number of lakes in the system.

The next n - 1 lines describe the rivers. The i-th of these lines contains three integers u_i, v_i, l_i (1 ≤ u_i, v_i ≤ n, u_i ≠ v_i, 1 ≤ l_i ≤ 10^3) — 1-based indices of lakes connected by the i-th river, and the length of this river.

The next line contains a single integer k (1 ≤ k ≤ 10^5) — the number of observations.

The next k lines describe the observations. The j-th of these lines contains three integers d_j, f_j, p_j (1 ≤ d_j ≤ 10^8, 1 ≤ f_j ≤ 10^4, 1 ≤ p_j ≤ n) — the day, the number of fish, and the lake index of the j-th observation. No two observations happen on the same day at the same lake simultaneously.

Output

Print one integer — the smallest total number of fish not contradicting the observations.

Examples

Input

4
1 2 1
1 3 1
1 4 1
5
1 1 2
1 1 3
2 2 1
3 1 4
3 1 2


Output

2


Input

5
1 2 1
1 3 1
1 4 1
1 5 1
4
1 1 2
2 1 3
3 1 4
4 1 5


Output

2


Input

5
2 5 1
5 1 1
2 4 1
5 3 3
6
5 2 4
2 1 1
2 1 3
2 2 4
4 7 5
4 1 2


Output

10

Note

In the first example, there could be one fish swimming through lakes 2, 1, and 4, and the second fish swimming through lakes 3, 1, and 2.

In the second example a single fish can not possibly be part of all observations simultaneously, but two fish swimming 2 → 1 → 4 and 3 → 1 → 5 can.

In the third example one fish can move from lake 1 to lake 5, others staying in their lakes during all time: two fish in lake 4, six fish in lake 5, one fish in lake 3. The system of lakes is shown on the picture.

<image>

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int N = 5 + 1e6;
struct K {
  int time, x, type, id;
  int query(int d) { return time - d * type; }
};
inline bool operator==(K x, K y) {
  return x.time == y.time && x.type == y.type && x.id == y.id;
}
inline bool operator!=(K x, K y) { return !(x == y); }
bool check_lex(K x, K y) {
  if (x.id != y.id) return x.id < y.id;
  return x.type < y.type;
}
struct K2 {
  int k;
  K p1, p2;
  K2(K g1, K g2) {
    p1 = g1, p2 = g2;
    k = g2.time - g1.time;
  }
};
bool check_k2(K x, K y) { return x.type == -1 && y.type == 1; }
bool operator<(K2 x, K2 y) {
  if (x.k != y.k) return x.k < y.k;
  if (x.p1 != y.p1) return check_lex(x.p1, y.p1);
  return check_lex(x.p2, y.p2);
}
bool operator>(K2 x, K2 y) { return y < x; }
int overall_delta;
struct Cmp {
  inline bool operator()(K x, K y) {
    int kx = x.query(overall_delta), ky = y.query(overall_delta);
    if (kx != ky) return kx < ky;
    if (x.type != y.type) {
      if (x.id == y.id)
        return x.type > y.type;
      else
        return x.type < y.type;
    }
    if (x.type == -1)
      return x.id > y.id;
    else
      return x.id < y.id;
  }
};
struct Delta {
  int delta;
  Delta() { delta = 0; }
  K2 to_inside_form(K2 x) {
    return K2(to_inside_form(x.p1), to_inside_form(x.p2));
  }
  K2 to_outside_form(K2 x) {
    return K2(to_outside_form(x.p1), to_outside_form(x.p2));
  }
  K to_inside_form(K x) {
    x.time += delta * x.type;
    return x;
  }
  K to_outside_form(K x) {
    x.time -= delta * x.type;
    return x;
  }
  void add_delta(int x) { delta += x; }
};
struct SS : Delta {
  multiset<K, Cmp> s;
  size_t size() { return s.size(); }
  bool empty() { return s.empty(); }
  void clear() {
    delta = 0;
    s.clear();
  }
  void insert(K x) {
    x = to_inside_form(x);
    overall_delta = delta;
    s.insert(x);
  }
  void erase(K x) {
    x = to_inside_form(x);
    overall_delta = delta;
    auto it = s.find(x);
    assert(it != s.end());
    s.erase(it);
  }
  void get_pos(K x, K& y, bool& f1, K& z, bool& f2) {
    overall_delta = delta;
    x = to_inside_form(x);
    auto it = s.find(x);
    assert(it != s.end());
    if (it == s.begin())
      f1 = false;
    else {
      y = to_outside_form(*prev(it));
      f1 = true;
    }
    if (it == prev(s.end()))
      f2 = false;
    else {
      z = to_outside_form(*next(it));
      f2 = true;
    }
  }
  void traverse(vector<K>& ret) {
    overall_delta = delta;
    for (auto x : s) ret.push_back(to_outside_form(x));
  }
};
struct QQ : Delta {
  multiset<K2> s;
  void push(K2 x) {
    overall_delta = delta;
    x = to_inside_form(x);
    s.insert(x);
  }
  K2 top() {
    overall_delta = delta;
    return to_outside_form(*s.begin());
  }
  void erase(K2 x) {
    overall_delta = delta;
    x = to_inside_form(x);
    auto it = s.find(x);
    assert(it != s.end());
    s.erase(it);
  }
  void pop() { erase(top()); }
  bool empty() { return s.empty(); }
  size_t size() { return s.size(); }
  void clear() {
    delta = 0;
    s.clear();
  }
};
struct OP {
  SS s;
  QQ q;
  void insert(K x) {
    K y, z;
    bool f1, f2;
    s.insert(x);
    s.get_pos(x, y, f1, z, f2);
    if (f1 && f2 && check_k2(y, z)) {
      q.erase(K2(y, z));
    }
    if (f1 && check_k2(y, x)) q.push(K2(y, x));
    if (f2 && check_k2(x, z)) q.push(K2(x, z));
  }
  void erase(K x) {
    K y, z;
    bool f1, f2;
    s.get_pos(x, y, f1, z, f2);
    if (f1 && f2 && check_k2(y, z)) {
      q.push(K2(y, z));
    }
    if (f1 && check_k2(y, x)) q.erase(K2(y, x));
    if (f2 && check_k2(x, z)) q.erase(K2(x, z));
    s.erase(x);
  }
  void update(int t) {
    while (!q.empty() && q.top().k < t) {
      K2 k = q.top();
      erase(k.p1);
      erase(k.p2);
      if (k.p1.x == k.p2.x)
        ;
      else if (k.p1.x < k.p2.x) {
        k.p2.x -= k.p1.x;
        insert(k.p2);
      } else {
        k.p1.x -= k.p2.x;
        insert(k.p1);
      }
    }
  }
  void add_delta(int t) {
    update(t + t);
    s.add_delta(t);
    q.add_delta(t);
  }
  void traverse(vector<K>& f) { s.traverse(f); }
  int get_ans() {
    int ans = 0, sum = 0;
    vector<K> f;
    s.traverse(f);
    for (int i = 0; i < f.size(); ++i) {
      sum += f[i].type * f[i].x;
      ans = max(ans, sum);
    }
    return ans;
  }
  size_t size() { return s.size(); }
  void clear() {
    q.clear();
    s.clear();
  }
} op[N];
vector<K> ff[N], last[N];
void merge(OP& x, OP& y) {
  if (x.size() < y.size()) swap(x, y);
  vector<K> f;
  y.traverse(f);
  y.clear();
  for (auto t : f) x.insert(t);
}
struct Graph {
  struct Edge {
    int to, nxt, key;
  } edge[N * 2];
  int head[N], top;
  Graph() { memset(head, -1, sizeof(head)), top = -1; }
  inline void add(int x, int y, int k) {
    edge[++top] = (Edge){y, head[x], k};
    head[x] = top;
  }
  inline void add2(int x, int y, int k) {
    add(x, y, k);
    add(y, x, k);
  }
} G;
int ti = 0;
void dfs(int x, int pre, int len) {
  for (int i = 0; i < ff[x].size(); i += 2) {
    ff[x][i].id = ff[x][i + 1].id = ++ti;
    op[x].insert(ff[x][i]);
    op[x].insert(ff[x][i + 1]);
  }
  for (int j = G.head[x]; ~j; j = G.edge[j].nxt) {
    int y = G.edge[j].to;
    if (y != pre) {
      dfs(y, x, G.edge[j].key);
      op[y].add_delta(G.edge[j].key);
      merge(op[x], op[y]);
    }
  }
  op[x].update(len + len + (x == 1));
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i < n; ++i) {
    int x, y, w;
    scanf("%d%d%d", &x, &y, &w);
    G.add2(x, y, w);
  }
  int m;
  scanf("%d", &m);
  for (int i = 0; i < m; ++i) {
    int t, x, pos;
    scanf("%d%d%d", &t, &x, &pos);
    ff[pos].push_back((K){t, x, -1, i});
    ff[pos].push_back((K){t, x, 1, i});
  }
  dfs(1, 0, 0);
  printf("%d\n", op[1].get_ans());
  return 0;
}