please provide a cpp code for the problem

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 $(1<=$ i $<=$ M$)$ between cities Ui and Vi

has certain constraints, characterized by Ai entities each with Bi resistance points. The travel time to cross this road at time t depends on these constraints: it takes $[$ Ai$/$t$+1]+$ Bi time units to overcome the entities and move on to city Vi$,$ 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 $(2<=$ N $<=105,0<=$ M $<=105).$

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

$$ The i th $(1<=$ i $<=$ M$)$ line consists of Ui$,$ Vi$,$ Bi$,$ Ai $(1<=$ Ui$,$ Vi $<=$ N$,0<=$ Ai$,$ Bi $<=109).$

Output :

$$ Print the minimum time possible according to the problem statement.

Examples

Input :

$23$

$1223$

$1221$

$1111$

Output :

$3$

input:

$69$

$1100$

$1312$

$1523$

$52165$

$26110$

$3434$

$35310$

$561100$

$420110$

Output :

$20$

Hint :

$$ ty $=$ tx $+[$Ai$/$tx$+1]+$ Bi

$$ tx is the time when you depart from city $$x$$ for city $$y$$

a code was provided for the problem but it is totally wrong and doesnt run for the testcases given, I will give the code for reference but please provide a code for the problem that satisfies the given examples

$//$ Include necessary libraries

#include

using namespace std;

$//$ Define types for ease of use

#define ll long long

#define pll pair

#define ppll pair

#define INF $1$e$18$

$//$ Initialize the adjacency list and the distance vector

vector$>$ adj;

vector dist;

$//$ Function to implement Dijkstra's algorithm

void dijkstra$($int start$)\{$

$//$ Initialize the priority queue with the start city

priority$\_$queue, greater$>$ pq;

pq$.$push$(\{0,$ start$\})$;

dist$[$start$]=0$;

$//$ While there are cities in the queue

while$(!$pq$.$empty$())\{$

$//$ Get the city with the shortest distance

ll city $=$ pq$.$top$().$second;

ll time $=$ pq$.$top$().$first;

pq$.$pop$()$;

$//$ If the current shortest distance is not equal to the calculated distance, skip this city

if$($time $!=$ dist$[$city$])$ continue;

$//$ Update the distances for each neighboring city

for$($auto &road : adj$[$city$])\{$

ll nextCity $=$ road.first;

ll A $=$ road.second.first;

ll B $=$ road.second.second;

$//$ Binary search to find the minimum time to cross the road

ll low $=1,$ high $=1$e$9$;

while$($low $<$ high$)\{$

ll mid $=($low $+$ high$)/2$;

if$($mid $*($B $+($A $+$ mid $-1)/$ mid$)<=$ time $+$ B$)\{$

high $=$ mid;

$\}$ else $\{$

low $=$ mid $+1$;

$\}$

$\}$

$//$ Calculate the next time

ll nextTime $=$ low $*($B $+($A $+$ low $-1)/$ low$)$;

$//$ If the calculated next time is less than the current shortest distance to the next city, update it

if$($nextTime $<$ dist$[$nextCity$])\{$

dist$[$nextCity$]=$ nextTime;

pq$.$push$(\{$nextTime$,$ nextCity$\})$;

$\}$

$\}$

$\}$

$\}$

$//$ Main function

int main$()\{$

$//$ Speed up input$/$output operations

ios$\_$base::sync$\_$with$\_$stdio$($false$)$;

cin.tie$($NULL$)$;

$//$ Read the number of cities and roads

int N$,$ M;

cin $>>$ N $>>$ M;

$//$ Resize the adjacency list and the distance vector

adj.resize$($N$+1)$;

dist.assign$($N$+1,$ INF$)$;

$//$ Read the details of each road

for$($int i $=0$; i $<$ M; i$++)\{$

int U$,$ V$,$ A$,$ B;

cin $>>$ U $>>$ V $>>$ A $>>$ B;

adj$[$U$].$push$\_$back$(\{$V$,\{$A$,$ B$\}\})$;

adj$[$V$].$push$\_$back$(\{$U$,\{$A$,$ B$\}\})$;

$\}$

$//$ Call Dijkstra's algorithm starting from city $1$

dijkstra$(1)$;

$//$ If it's not possible to reach city N$,$ print $-1$

$//$ Otherwise, print the minimum time required

if$($dist$[$N$]==$ INF$)\{$

cout $<<-1<<"$

$"$;

$\}$ else $\{$

cout $<<$ dist$[$N$]<<"$

$"$;

$\}$

return $0$;

$\}$