Frodo Baggins is trying to run from the fury of Smaug. Let’s assume we represent our city by a weighted undirected connected graph(with no self-loops and multi-edges) with N nodes and N edges.
You will be given Q queries of form St, De, S, Vf, VS which denotes:
Frodo is currently at node St and needs to reach node De. He moves with constant velocity Vf. Smaug is currently at node S and he moves with constant velocity VS. Print "YES"(quotes for clarity), if Frodo can reach destination without being caught by Smaug no matter what path Smaug takes. Else print "NO"(quotes for clarity).
Note: If Frodo reaches at destination at same time as Smaug, print "NO".
First line contains N and Q, the number of nodes and number of queries respectively. Each of the next N lines contain integers u, v and w denoting an undirected edge between nodes numbered u and v, w being the weight of the edge.
Each of the next Q lines contain queries.
For each query print the required answer in one line.
*Constraints*
## Input
First line contains N and Q, the number of nodes and number of queries respectively. Each of the next N lines contain integers u, v and w denoting an undirected edge between nodes numbered u and v, w being the weight of the edge.Each of the next Q lines contain queries.
## Output
For each query print the required answer in one line.*Constraints* 1 ≤ N, Q ≤ 105 1 ≤ u, v, St, De, S ≤ N 1 ≤ VF, VS, w ≤ 1000
[samples]
**Definitions**
Let $ G = (V, E) $ be a weighted undirected connected graph with $ |V| = N $ nodes and $ |E| = N $ edges.
Let $ w: E \to \mathbb{R}^+ $ be the edge weight function (positive real numbers).
For each query $ q \in \{1, \dots, Q\} $:
- $ s_t^{(q)} \in V $: Frodo’s starting node.
- $ d^{(q)} \in V $: Frodo’s destination node.
- $ v_f^{(q)} \in \mathbb{R}^+ $: Frodo’s constant velocity.
- $ s^{(q)} \in V $: Smaug’s starting node.
- $ v_s^{(q)} \in \mathbb{R}^+ $: Smaug’s constant velocity.
**Constraints**
1. $ 1 \le N \le \text{upper bound} $ (not specified, but implied by context).
2. $ 1 \le Q \le \text{upper bound} $ (not specified).
3. Edge weights $ w(e) > 0 $ for all $ e \in E $.
4. Velocities $ v_f^{(q)} > 0 $, $ v_s^{(q)} > 0 $ for all queries.
**Objective**
For each query $ q $, compute:
- $ D_f^{(q)} = \min_{P \in \mathcal{P}(s_t^{(q)}, d^{(q)})} \sum_{e \in P} w(e) $: shortest path distance from $ s_t^{(q)} $ to $ d^{(q)} $.
- $ D_s^{(q)} = \min_{P \in \mathcal{P}(s^{(q)}, d^{(q)})} \sum_{e \in P} w(e) $: shortest path distance from $ s^{(q)} $ to $ d^{(q)} $.
Let $ t_f^{(q)} = \frac{D_f^{(q)}}{v_f^{(q)}} $: Frodo’s minimum time to reach $ d^{(q)} $.
Let $ t_s^{(q)} = \frac{D_s^{(q)}}{v_s^{(q)}} $: Smaug’s minimum time to reach $ d^{(q)} $.
Output:
$$
\begin{cases}
\text{YES} & \text{if } t_f^{(q)} < t_s^{(q)} \\
\text{NO} & \text{otherwise}
\end{cases}
$$