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.