Sample Input $0$

$4$

$6$

$0120$

$1020$

$1210$

$2010$

$1330$

$3230$

Sample Output $0$

$40$

$0$

$1$

Explanation $0$

Explanation $0$ For example, Let us calculate the round trip between City $1$ and City $3$ ie $R(1,3)$

Cost$(1,3)=P(1,3)=30,$ because there are only one simple way to go to there.

Cost$(3,1)=P(3,2)+P(2,0)+P(0,1)=60.$

So the cheapest round trip from City $1$ and City $3$ i$.$e $R(1,3)$ is equal to $30+60=90$ units.

We can calculate all the other round trip in the similar way, then we can get the answer which is $R(0,1)$ i$.$e

There are $2$ city pairs with the lowest cost $(0,1)$ and $(0,2).$

Lowest sum of indices belongs to $(0,1)$ & hence $0$ and $1$ in alphanumeric order.

Sample Input $1$

$3$

$3$

$01100$

$12100$

$02100$

Sample Output $1$

$1000000$

$-1$

$-1$

Explanation $1$

There is no return flights from any combination of cities. Hence the answers.Cheap Airfare

Problem Statement

Anjali has started a new travel agency. She noticed that the air fares between the cities are not

symmetrical. That is$,$ the cost of flying from $a$ to $b$ is not the same as that of $b$ to $a.$ Further, there is no

guarantee that once you fly directly from $a$ to $b$ there is a direct return flight.

She knows that passengers do not mind changing flights as long as the total airfare is minimized. She

needs to advertise the lowest round trip cost between any pair of cities of tourist interest to attract

potential passengers. All valid flights i$.$e$.(A,B,P(A,B))$ where $A$ is the source city of tourist interest, $B$ is the

destination city of tourist interest and $P(A,B)$ is the price of the ticket.

You must help her determine the lowest round trip cost & the cities involved.

Input Format

The first line consists of integer $n$ indicating the number of cities

The second line consists of integer $m$ indicating the number of flights

Each of the next $\text{'}m\text{'}$ lines contains $3$ integers separated by a space $-$ starting city A$,$ end city B and the

price of the ticket $P(A,B)$ for flight from $A$ to $B.$

Constraints

$1$ Number of cities $<mn\; id="EditorElement\_672177">1</mn><mn\; id="EditorElement\_672178">0</mn><mn\; id="EditorElement\_672179">0</mn>$

$0$ Number of flights $<mn\; id="EditorElement\_672127">5</mn><mn\; id="EditorElement\_672128">0</mn><mn\; id="EditorElement\_672129">0</mn><mn\; id="EditorElement\_672130">0</mn>$

$0$ Price $<mn\; id="EditorElement\_672087">1</mn><mn\; id="EditorElement\_672088">0</mn><mn\; id="EditorElement\_672089">0</mn><mn\; id="EditorElement\_672090">0</mn><mn\; id="EditorElement\_672091">0</mn>$

Output Format

Return an array of $3$ integers. $1$st integer is the price for the cheapest round trip. $2$nd and $3$rd integers are

the city indices involved in increasing order.

If there is no round trip available, return $1000000,-1$ and $-1.$

If there are multiple pair of cities with lowest round trip fair, please select the pair with the lowest sum of

their indices.