give the code in c$++,$ read the imput and ouput format properly, dont copy paste from anywhere, You need to travel from city $1$ to city $N$ across a land divided into $N$ cities

connected by $M$ undirected roads. Each road $i(1iM)$ between cities $U_i$ and $V_i$

has certain constraints, characterized by $A_i$ entities each with $B_i$ resistance points. The

travel time to cross this road at time $t$ depends on these constraints: it takes ${|}_{{?}_{?}}\frac{A_i}{(t+1{)}_{{?}_{?}}}|+B_i$

time units to overcome the entities and move on to city $V_i,$ where the division is done

using integer division. You can start your journey at time $0$ or any integer time unit

thereafter, and you can wait at any city for any integer amount of time. The goal is to

minimize the overall journey time. If it is not possible to reach city $N,$ the result should

be $-1.$ The task is to find the minimum time required to complete your journey.

Input :

First line of input consists of $N$ and $M(2N{10}^5,0M{10}^5).$

The next $M$ lines contain the description of the undirected roads.

The $i^{th}(1iM)$ line consists of

$\{$:${10}^9).$

Output :

Print the minimum time possible according to the problem statement.

Examples

Input :

Output :

$3$

By selecting the second road that links city $1$ to city $2$ and initiating the journey from

city $1$ at time $t=0,$ you can arrive in city $2$ with a calculated time of

${|}_{{?}_{?}}\frac{1}{(0+1{)}_{{?}_{?}}}|+2=3$

units, where the division is integer division. Thus, the minimal travel time required to

reach city $2$ is $3$ units.

Input :

Output :

$20$

Hint :

$t_y=t_x+{|}_{{?}_{?}}\frac{A_i}{(t_x+1{)}_{{?}_{?}}}|+B_i$

$t_x$ is the time when you depart from city $\text{'}x\text{'}$ for city $\text{'}y\text{'}$