Problem: Tony Stark is playing a game with his suits (they have auto-pilot now). He lives in Malibu. Malibu has n junctions numbered from 1 to n, connected with n - 1 roads. One can get from a junction to any other junction using these roads (graph of Malibu forms a tree).

Tony has m suits. There's a special plan for each suit. The i-th suit will appear at the moment of time ti in the junction vi, and will move to junction ui using the shortest path between vi and ui with the speed ci roads per second (passing a junctions takes no time), and vanishing immediately when arriving at ui (if it reaches ui in time q, it's available there at moment q, but not in further moments). Also, suits move continuously (for example if vi ≠ ui, at time <image> it's in the middle of a road. Please note that if vi = ui it means the suit will be at junction number vi only at moment ti and then it vanishes. 

An explosion happens if at any moment of time two suits share the same exact location (it may be in a junction or somewhere on a road; while appearing, vanishing or moving).

Your task is to tell Tony the moment of the the first explosion (if there will be any).

Input

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 100 000) — the number of junctions and the number of suits respectively.

The next n - 1 lines contain the roads descriptions. Each line contains two integers ai and bi — endpoints of the i-th road (1 ≤ ai, bi ≤ n, ai ≠ bi).

The next m lines contain the suit descriptions. The i-th of them contains four integers ti, ci, vi and ui (0 ≤ ti ≤ 10 000, 1 ≤ ci ≤ 10 000, 1 ≤ vi, ui ≤ n), meaning the i-th suit will appear at moment of time ti at the junction vi and will move to the junction ui with a speed ci roads per second.

Output

If there would be no explosions at all, print -1 in the first and only line of output.

Otherwise print the moment of the first explosion.

Your answer will be considered correct if its relative or absolute error doesn't exceed 10 - 6.

Examples

Input

6 4
2 5
6 5
3 6
4 6
4 1
27 6 1 3
9 5 1 6
27 4 3 4
11 29 2 6


Output

27.3


Input

6 4
3 1
4 5
6 4
6 1
2 6
16 4 4 5
13 20 6 2
3 16 4 5
28 5 3 5


Output

-1

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1.01e18;
bool eq(long double A, long double B) { return abs(A - B) < 1e-9; }
bool ls(long double A, long double B) { return A < B && !eq(A, B); }
bool le(long double A, long double B) { return A < B || eq(A, B); }
struct pt {
  long double x, y;
  pt() {}
  pt(long double xx, long double yy) : x(xx), y(yy) {}
  pt operator+(pt A) { return pt(x + A.x, y + A.y); }
  pt operator-(pt A) { return pt(x - A.x, y - A.y); }
  pt operator*(long double k) { return pt(x * k, y * k); }
  long double operator*(pt A) { return x * A.y - y * A.x; }
  long double operator%(pt A) { return x * A.x + y * A.y; }
  bool operator==(pt A) { return eq(x, A.x) && eq(y, A.y); }
  bool operator!=(pt A) { return !eq(x, A.x) || !eq(y, A.y); }
  long double len() { return sqrt(x * x + y * y); }
  long double len2() { return x * x + y * y; }
  pt rotate() { return pt(-y, x); }
  void read() {
    double xx, yy;
    scanf("%lf%lf", &xx, &yy);
    x = xx;
    y = yy;
  }
  void Epr() { cerr << "x y: " << x << " " << y << endl; }
};
struct Line {
  pt O, v;
  Line(pt A, pt B) : O(A), v(B - A) {}
  pt operator*(Line l) {
    pt u = l.v.rotate();
    long double t = (l.O - O) % u / (v % u);
    return O + v * t;
  }
};
int sign(long double x) {
  if (eq(x, 0)) return 0;
  if (x < 0) return -1;
  return 1;
}
bool box(long double a, long double b, long double c, long double d) {
  if (a > b) swap(a, b);
  if (c > d) swap(c, d);
  return le(max(a, c), min(b, d));
}
bool intSS(pt A, pt B, pt C, pt D) {
  return box(A.x, B.x, C.x, D.x) && box(A.y, B.y, C.y, D.y) &&
         sign((B - A) * (C - A)) * sign((B - A) * (D - A)) <= 0 &&
         sign((D - C) * (A - C)) * sign((D - C) * (B - C)) <= 0;
}
long double getX(pt A, pt B, pt C, pt D) {
  Line ab(A, B);
  Line cd(C, D);
  if (!eq(ab.v * cd.v, 0)) {
    return (ab * cd).x;
  }
  return max(min(A.x, B.x), min(C.x, D.x));
}
long double slow(vector<pair<pt, pt>> seg) {
  long double answer = INF;
  for (int i = 0; i < (int)(seg).size(); i++) {
    for (int j = i + 1; j < (int)(seg).size(); j++) {
      if (intSS(seg[i].first, seg[i].second, seg[j].first, seg[j].second)) {
        answer = min(answer, getX(seg[i].first, seg[i].second, seg[j].first,
                                  seg[j].second));
      }
    }
  }
  return answer;
}
long double solve(vector<pair<pt, pt>> seg) {
  struct Seg {
    pt A, B;
  };
  struct CMP {
    bool operator()(Seg s1, Seg s2) const {
      if (eq(s1.A.x, s1.B.x)) {
        if (eq(s2.A.x, s2.B.x)) {
          return ls(s1.A.y, s2.A.y);
        }
        return ls(0, (s1.A - s2.A) * (s2.B - s2.A));
      }
      if (eq(s2.A.x, s2.B.x)) {
        return ls(0, (s1.B - s1.A) * (s2.A - s1.A));
      }
      if (s1.A.x < s2.A.x) {
        return ls(0, (s1.B - s1.A) * (s2.A - s1.A));
      } else {
        return ls(0, (s1.A - s2.A) * (s2.B - s2.A));
      }
    }
  };
  struct Event {
    int type;
    pt A, B;
  };
  vector<Event> event;
  for (auto s : seg) {
    pt A = s.first;
    pt B = s.second;
    if (A.x > B.x) swap(A, B);
    event.push_back({1, A, B});
    event.push_back({-1, B, A});
  }
  sort((event).begin(), event.end(), [](Event C, Event D) {
    if (eq(C.A.x, D.A.x)) {
      return C.type > D.type;
    }
    return C.A.x < D.A.x;
  });
  set<Seg, CMP> q;
  long double win = INF;
  auto checkS = [&](Seg s1, Seg s2) {
    if (intSS(s1.A, s1.B, s2.A, s2.B)) {
      win = min(win, getX(s1.A, s1.B, s2.A, s2.B));
    }
  };
  auto check = [&](Seg s) {
    auto it = q.lower_bound(s);
    if (it != q.end()) {
      checkS(s, *it);
      it++;
      if (it != q.end()) {
        checkS(s, *it);
      }
    }
    it = q.lower_bound(s);
    if (it != q.begin()) {
      it--;
      checkS(s, *it);
      if (it != q.begin()) {
        it--;
        checkS(s, *it);
      }
    }
  };
  for (auto E : event) {
    if (le(win, E.A.x)) {
      break;
    }
    if (E.type == 1) {
      check({E.A, E.B});
      q.insert({E.A, E.B});
    } else {
      Seg s = {E.B, E.A};
      q.erase(s);
      auto it = q.lower_bound(s);
      if (it != q.end() && it != q.begin()) {
        auto it2 = it;
        it2--;
        checkS(*it, *it2);
      }
    }
  }
  return win;
}
long double solve2(vector<pair<pt, pt>> seg) {
  struct Event {
    pt A, B;
    int type;
  };
  vector<Event> event;
  for (auto s : seg) {
    pt A = s.first;
    pt B = s.second;
    if (A.x > B.x) swap(A, B);
    event.push_back({A, B, 1});
    event.push_back({B, A, -1});
  }
  sort((event).begin(), event.end(), [](Event C, Event D) {
    return ls(C.A.x, D.A.x) || (eq(C.A.x, D.A.x) && C.type > D.type);
  });
  struct Seg {
    pt A, B;
    long double getY(long double x) const {
      assert(le(A.x, x) && le(x, B.x));
      if (eq(A.x, B.x)) {
        return A.y;
      }
      return (A.y * (B.x - x) + B.y * (x - A.x)) / (B.x - A.x);
    }
  };
  static long double curX = 0;
  struct CMP2 {
    bool operator()(Seg s1, Seg s2) const {
      return ls(s1.getY(curX), s2.getY(curX));
    }
  };
  set<Seg, CMP2> q;
  long double win = INF;
  auto checkS = [&](Seg s1, Seg s2) {
    if (intSS(s1.A, s1.B, s2.A, s2.B)) {
      win = min(win, getX(s1.A, s1.B, s2.A, s2.B));
    }
  };
  auto check = [&](Seg s) {
    auto it = q.lower_bound(s);
    if (it != q.end()) {
      checkS(s, *it);
      it++;
      if (it != q.end()) {
        checkS(s, *it);
      }
    }
    it = q.lower_bound(s);
    if (it != q.begin()) {
      it--;
      checkS(s, *it);
      if (it != q.begin()) {
        it--;
        checkS(s, *it);
      }
    }
  };
  for (auto E : event) {
    curX = E.A.x;
    if (le(win, curX)) {
      break;
    }
    if (E.type == 1) {
      Seg s = {E.A, E.B};
      check(s);
      q.insert(s);
    } else {
      Seg s = {E.B, E.A};
      auto it = q.lower_bound(s);
      if (it != q.end() && it != q.begin()) {
        auto it2 = it;
        it2--;
        it++;
        if (it != q.end()) {
          checkS(*it, *it2);
        }
      }
      q.erase(s);
    }
  }
  return win;
}
void stress() {
  for (int tt = 0;; tt++) {
    cerr << "tt"
         << " = " << tt << endl;
    vector<pair<pt, pt>> seg;
    int n = rand() % 1000 + 1;
    int T = 100000;
    for (int i = 0; i < n; i++) {
      long double speed = rand() % T + 1;
      long double y1 = rand() % T;
      long double y2 = rand() % T;
      int len = rand() % T;
      int shift = rand() % 10;
      long double x1 = shift + (len + y1) / speed;
      long double x2 = shift + (len + y2) / speed;
      seg.push_back({{x1, y1}, {x2, y2}});
    }
    auto r1 = slow(seg);
    auto r2 = solve2(seg);
    cerr << "("
         << "r1"
         << ", "
         << "r2"
         << ") = (" << r1 << ", " << r2 << ")\n";
    ;
    assert(eq(r1, r2));
  }
}
struct Robot {
  int t, c, v, u;
  void read() {
    scanf("%d%d%d%d", &t, &c, &v, &u);
    v--;
    u--;
  }
};
long double fast(int n, vector<pair<int, int>> edge, vector<Robot> robot) {
  vector<vector<int>> e(n);
  for (auto x : edge) {
    int v = x.first;
    int u = x.second;
    e[v].push_back(u);
    e[u].push_back(v);
  }
  vector<int> h(n);
  vector<int> p(n, -1);
  vector<int> heavy(n, -1);
  vector<int> root(n);
  vector<int> pos(n);
  vector<vector<pair<pt, pt>>> seg(n);
  function<int(int, int)> dfs0 = [&](int v, int par) {
    int sz = 1;
    int mx = 0;
    for (auto u : e[v]) {
      if (u == par) continue;
      h[u] = h[v] + 1;
      p[u] = v;
      int ch = dfs0(u, v);
      if (ch > mx) {
        mx = ch;
        heavy[v] = u;
      }
      sz += ch;
    }
    return sz;
  };
  dfs0(0, -1);
  for (int i = 0; i < n; i++) {
    if (p[i] == -1 || heavy[p[i]] != i) {
      int cur = 0;
      for (int v = i; v != -1; v = heavy[v]) {
        root[v] = i;
        pos[v] = cur++;
      }
    }
  }
  auto add = [&](int v, int y1, int y2, long double x1, long double x2) {
    seg[v].push_back({pt(x1, y1), pt(x2, y2)});
  };
  int m = robot.size();
  for (int i = 0; i < m; i++) {
    long double t = robot[i].t;
    long double c = robot[i].c;
    int v = robot[i].v;
    int u = robot[i].u;
    int vv = v;
    int uu = u;
    int len = 0;
    for (; root[vv] != root[uu]; vv = p[root[vv]]) {
      if (h[root[uu]] > h[root[vv]]) swap(vv, uu);
      len += pos[vv] + 1;
    }
    len += abs(pos[vv] - pos[uu]);
    int progV = 0;
    int progU = 0;
    for (; root[v] != root[u];) {
      if (h[root[v]] > h[root[u]]) {
        add(root[v], pos[v] + 1, 0, t + progV * 1.0 / c,
            t + (progV + pos[v] + 1) * 1.0 / c);
        progV += pos[v] + 1;
        v = p[root[v]];
      } else {
        add(root[u], pos[u] + 1, 0, t + (len - progU) * 1.0 / c,
            t + (len - progU - pos[u] - 1) * 1.0 / c);
        progU += pos[u] + 1;
        u = p[root[u]];
      }
    }
    add(root[v], pos[v] + 1, pos[u] + 1, t + (progV)*1.0 / c,
        t + (progV + abs(pos[u] - pos[v])) * 1.0 / c);
  }
  long double answer = INF;
  for (int i = 0; i < n; i++) {
    answer = min(answer, solve2(seg[i]));
  }
  return answer;
}
void mySwap(int &v, int &u) {
  if (v > u) swap(v, u);
}
long double slow(int n, vector<pair<int, int>> edge, vector<Robot> robot) {
  vector<vector<int>> e(n);
  for (auto x : edge) {
    e[x.first].push_back(x.second);
    e[x.second].push_back(x.first);
  }
  vector<int> st;
  vector<int> path;
  function<void(int, int, int)> dfs = [&](int v, int p, int target) {
    st.push_back(v);
    if (v == target) {
      path = st;
      return;
    }
    for (auto u : e[v]) {
      if (u != p) {
        dfs(u, v, target);
        if (!path.empty()) {
          return;
        }
      }
    }
    st.pop_back();
  };
  map<pair<int, int>, vector<pair<pt, pt>>> seg;
  vector<vector<long double>> moment(n);
  for (auto x : robot) {
    int v = x.v;
    int u = x.u;
    long double c = x.c;
    path.clear();
    st.clear();
    dfs(v, -1, u);
    assert(!path.empty());
    for (int i = 0; i < (int)(path).size() - 1; i++) {
      int vv = path[i];
      int uu = path[i + 1];
      if (vv > uu) {
        swap(vv, uu);
        seg[{vv, uu}].push_back(
            {{x.t + (i)*1.0 / c, 1}, {x.t + (i + 1) * 1.0 / c, 0}});
      } else {
        seg[{vv, uu}].push_back(
            {{x.t + (i)*1.0 / c, 0}, {x.t + (i + 1) * 1.0 / c, 1}});
      }
    }
    for (int i = 0; i < (int)(path).size(); i++) {
      long double tmr = x.t + i * 1.0 / x.c;
      moment[path[i]].push_back(tmr);
    }
  }
  long double answer = INF;
  for (int i = 0; i < n; i++) {
    sort((moment[i]).begin(), moment[i].end());
    for (int j = 0; j < (int)(moment[i]).size() - 1; j++) {
      if (eq(moment[i][j], moment[i][j + 1])) {
        answer = min(answer, moment[i][j]);
      }
    }
  }
  for (auto x : seg) {
    auto g = x.second;
    for (int i = 0; i < (int)(g).size(); i++) {
      for (int j = 0; j < i; j++) {
        if (intSS(g[i].first, g[i].second, g[j].first, g[j].second)) {
          answer = min(answer,
                       getX(g[i].first, g[i].second, g[j].first, g[j].second));
        }
      }
    }
  }
  return answer;
}
int main() {
  if (1) {
    int n, m;
    scanf("%d%d", &n, &m);
    vector<pair<int, int>> edge;
    for (int i = 0; i < n - 1; i++) {
      int v, u;
      scanf("%d%d", &v, &u);
      v--;
      u--;
      edge.push_back({v, u});
    }
    vector<Robot> robot(m);
    for (int i = 0; i < m; i++) {
      robot[i].read();
    }
    auto res = fast(n, edge, robot);
    if (res == INF) {
      puts("-1");
    } else {
      printf("%.17f", (double)res);
    }
  } else {
    for (int tt = 0;; tt++) {
      cerr << "tt"
           << " = " << tt << endl;
      int n = rand() % 10 + 1;
      int m = rand() % 5 + 1;
      vector<pair<int, int>> edge;
      for (int i = 1; i < n; i++) {
        int v = rand() % i;
        edge.push_back({v, i});
      }
      vector<Robot> robot(m);
      for (int i = 0; i < m; i++) {
        robot[i] = {rand() % 10, rand() % 10 + 1, rand() % n, rand() % n};
      }
      auto r1 = fast(n, edge, robot);
      auto r2 = slow(n, edge, robot);
      cerr << n << " " << m << endl;
      for (auto x : edge) {
        cerr << x.first + 1 << " " << x.second + 1 << endl;
      }
      for (auto x : robot) {
        cerr << x.t << " " << x.c << " " << x.v + 1 << " " << x.u + 1 << endl;
      }
      cerr << "("
           << "r1"
           << ", "
           << "r2"
           << ") = (" << r1 << ", " << r2 << ")\n";
      ;
      assert(eq(r1, r2));
    }
  }
  return 0;
}