We are given an connected undirected weighted graph of $N$ nodes and $M$ edges. We are then given $Q$ queries where in each query we are given integers $U,L,R,K$. For every query we have to report the smallest integer $C$ such that there are atleast $K$ nodes $x$ such that $L \leq x \leq R$ and shortest distance from $x$ to $U$ is not more than $C$. 

Constraints : 

$N \leq 1000$

$M \leq 5000$

Weight of edge $\leq 10000$

$Q \leq 2 \cdot 10^5$

$1 \leq a,b,U,L,R \leq N$

$K \leq R-L+1$

Input: 

The first line contains two integers $N,M$. The next $M$ lines contains three space separated integers $a,b,c$ meaning that there is an edge between nodes $a$ and $b$ of weight $c$. The next line contains an integer $Q$. $Q$ lines follow, each with four integers $U,L,R,K$ with the meaning as given in problem. 

Output : 

$Q$ lines should be printed and the $i^{th}$ line should contain the output for the $i^{th}$ query.