Problem: Mayor of Yusland just won the lottery and decided to spent money on something good for town. For example, repair all the roads in the town.

Yusland consists of n intersections connected by n - 1 bidirectional roads. One can travel from any intersection to any other intersection using only these roads.

There is only one road repairing company in town, named "RC company". Company's center is located at the intersection 1. RC company doesn't repair roads you tell them. Instead, they have workers at some intersections, who can repair only some specific paths. The i-th worker can be paid ci coins and then he repairs all roads on a path from ui to some vi that lies on the path from ui to intersection 1. 

Mayor asks you to choose the cheapest way to hire some subset of workers in order to repair all the roads in Yusland. It's allowed that some roads will be repaired more than once.

If it's impossible to repair all roads print  - 1.

Input

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 300 000) — the number of cities in Yusland and the number of workers respectively.

Then follow n−1 line, each of them contains two integers xi and yi (1 ≤ xi, yi ≤ n) — indices of intersections connected by the i-th road.

Last m lines provide the description of workers, each line containing three integers ui, vi and ci (1 ≤ ui, vi ≤ n, 1 ≤ ci ≤ 109). This means that the i-th worker can repair all roads on the path from vi to ui for ci coins. It's guaranteed that vi lies on the path from ui to 1. Note that vi and ui may coincide.

Output

If it's impossible to repair all roads then print  - 1. Otherwise print a single integer — minimum cost required to repair all roads using "RC company" workers.

Example

Input

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


Output

8

Note

In the first sample, we should choose workers with indices 1, 3, 4 and 5, some roads will be repaired more than once but it is OK. The cost will be equal to 2 + 3 + 1 + 2 = 8 coins.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:16777216")
const int inf = 0x3f3f3f3f;
const string debug_line = "yolo";
const long long linf = 1e15 + 5;
typedef struct node2 {
  long long val;
  long long lazyp;
  bool islazyp;
} node1;
node1 tree[2400100];
vector<int> Adj[600100];
bool visited[600100];
vector<pair<int, int> > add[600100];
vector<pair<int, int> > del[600100];
int dfs_timer = 0;
int begin1[600100];
int end1[600100];
int timerWork[600100];
long long dp[600100];
bool isanswer = true;
int n, m;
long long ST[600010 << 2], L[600010 << 2];
void initialise(int node, int b, int e) {
  if (b > e) {
    return;
  } else if (b == e) {
    tree[node].val = 40000000000000000LL;
    tree[node].lazyp = 0;
    tree[node].islazyp = 0;
    return;
  } else {
    initialise(2 * node, b, (b + e) / 2);
    initialise(2 * node + 1, (b + e) / 2 + 1, e);
    tree[node].val = 40000000000000000LL;
    tree[node].lazyp = 0;
    tree[node].islazyp = 0;
    return;
  }
}
void updatev(int node, int b, int e, int index, long long val) {
  if (tree[node].islazyp) {
    tree[node].val += tree[node].lazyp;
    tree[node].val = min(tree[node].val, 40000000000000000LL);
    if (b != e) {
      tree[2 * node].lazyp += tree[node].lazyp;
      tree[2 * node + 1].lazyp += tree[node].lazyp;
      tree[2 * node].lazyp = min(tree[2 * node].lazyp, 40000000000000000LL);
      tree[2 * node + 1].lazyp =
          min(tree[2 * node + 1].lazyp, 40000000000000000LL);
      tree[2 * node].islazyp = tree[2 * node + 1].islazyp = true;
    }
    tree[node].islazyp = false;
    tree[node].lazyp = 0;
  }
  if (b > e || b > index || e < index) {
    return;
  } else if (b == e && e == index) {
    tree[node].val = min(val, 40000000000000000LL);
    return;
  } else {
    updatev(2 * node, b, (b + e) / 2, index, val);
    updatev(2 * node + 1, (b + e) / 2 + 1, e, index, val);
    tree[node].val = min(min(tree[2 * node].val, tree[2 * node + 1].val),
                         40000000000000000LL);
    return;
  }
}
void updated(int node, int b, int e, int i, int j, long long val) {
  if (tree[node].islazyp) {
    tree[node].val += tree[node].lazyp;
    tree[node].val = min(tree[node].val, 40000000000000000LL);
    if (b != e) {
      tree[2 * node].lazyp += tree[node].lazyp;
      tree[2 * node + 1].lazyp += tree[node].lazyp;
      tree[2 * node].lazyp = min(tree[2 * node].lazyp, 40000000000000000LL);
      tree[2 * node + 1].lazyp =
          min(tree[2 * node + 1].lazyp, 40000000000000000LL);
      tree[2 * node].islazyp = tree[2 * node + 1].islazyp = true;
    }
    tree[node].islazyp = false;
    tree[node].lazyp = 0;
  }
  if (b > e || i > e || j < b) {
    return;
  } else if (i <= b && e <= j) {
    tree[node].val += val;
    tree[node].val = min(tree[node].val, 40000000000000000LL);
    if (b != e) {
      tree[2 * node].lazyp += val;
      tree[2 * node + 1].lazyp += val;
      tree[2 * node].islazyp = tree[2 * node + 1].islazyp = true;
    }
    return;
  } else {
    updated(2 * node, b, (b + e) / 2, i, j, val);
    updated(2 * node + 1, (b + e) / 2 + 1, e, i, j, val);
    tree[node].val = min(min(tree[2 * node].val, tree[2 * node + 1].val),
                         40000000000000000LL);
    return;
  }
}
void query(node1 &res, int node, int b, int e, int i, int j) {
  if (tree[node].islazyp) {
    tree[node].val += tree[node].lazyp;
    tree[node].val = min(tree[node].val, 40000000000000000LL);
    if (b != e) {
      tree[2 * node].lazyp += tree[node].lazyp;
      tree[2 * node + 1].lazyp += tree[node].lazyp;
      tree[2 * node].lazyp = min(tree[2 * node].lazyp, 40000000000000000LL);
      tree[2 * node + 1].lazyp =
          min(tree[2 * node + 1].lazyp, 40000000000000000LL);
      tree[2 * node].islazyp = tree[2 * node + 1].islazyp = true;
    }
    tree[node].islazyp = false;
    tree[node].lazyp = 0;
  }
  if (b > e || i > e || j < b) {
    return;
  } else if (i <= b && e <= j) {
    res = tree[node];
    return;
  } else {
    node1 l, r;
    l.val = r.val = 40000000000000000LL;
    query(l, 2 * node, b, (b + e) / 2, i, j);
    query(r, 2 * node + 1, (b + e) / 2 + 1, e, i, j);
    res.val = min(min(l.val, r.val), 40000000000000000LL);
    return;
  }
}
long long solve(int u, int p) {
  visited[u] = true;
  long long prev = 0;
  for (auto &(t1) : (Adj[u])) {
    if (!visited[t1] && t1 != p) {
      prev += solve(t1, u);
      if (prev != 2 * linf) {
        prev = min(prev, 2 * linf);
      }
    }
  }
  if (u == 1) {
    dp[u] = prev;
    return dp[u];
  }
  for (auto &(t1) : (add[u])) {
    updatev(1, 1, m, timerWork[t1.first], t1.second + prev);
  }
  for (auto &(t1) : (del[u])) {
    updatev(1, 1, m, timerWork[t1.first], linf);
  }
  for (auto &(t1) : (Adj[u])) {
    if (t1 != p) {
      updated(1, 1, m, begin1[t1], end1[t1], prev - dp[t1]);
    }
  }
  node1 res;
  res.val = 40000000000000000LL;
  query(res, 1, 1, m, begin1[u], end1[u]);
  dp[u] = res.val;
  return dp[u];
}
void DFS(int u, int p) {
  visited[u] = true;
  begin1[u] = dfs_timer + 1;
  for (auto &(t1) : (add[u])) {
    timerWork[t1.first] = ++dfs_timer;
  }
  for (auto &(t1) : (Adj[u])) {
    if (!visited[t1] && t1 != p) {
      DFS(t1, u);
    }
  }
  end1[u] = dfs_timer;
  return;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int(i) = (1); (i) < (n); ++(i)) {
    int a, b;
    scanf("%d%d", &a, &b);
    Adj[a].push_back(b);
    Adj[b].push_back(a);
  }
  for (int(i) = (0); (i) < (m); ++(i)) {
    int u, v, c;
    scanf("%d%d%d", &u, &v, &c);
    add[u].push_back(make_pair(i, c));
    del[v].push_back(make_pair(i, c));
  }
  initialise(1, 1, m);
  DFS(1, 0);
  cerr << "debug_line"
       << " = " << (debug_line) << endl;
  for (int(i) = (0); (i) < (n + 1); ++(i)) {
    visited[i] = false;
  }
  long long answer1 = solve(1, 0);
  if (answer1 >= linf || !isanswer) {
    printf("-1\n");
  } else {
    printf("%lld\n", answer1);
  }
  return 0;
}