Egy ország úthálózata kétirányú, egyenes autópályákból áll, melyek egy-egy várospárt kötnek össze. Minden útnak ismerjük a két végpontját, illetve a megtételéhez szükséges időt. Az országban két város (A és B) gyors fejlődésnek indult, így az ország vezetői minimalizálni szeretnék a két város közötti út megtételének idejét. Sajnos földrajzi okokból nem tudnak újabb autópályákat építeni. Kifejlesztettek egy közlekedési eszközt, egyenes számára kiépített speciális pályán elhanyagolható idő alatt (0) juttatja el a rakományát, vagy utasait a pálya két végpontja között. Mivel ez az új jármű nagyon drága, csak egyetlen darabot tudnak belőle megépíteni. A jármű vonalát csak egy már meglévő autópályával párhuzamosan lehet kiépíteni.
Írjunk programot, ami segít az ország vezetőinek megmondani, hogy melyik két város közötti autópálya mellé építsék ki a kifejlesztett közlekedési eszköz vonalát, illetve megmondja, hogy mennyivel csökken az utazási idő A és B között. A városokat 1 és $N$ közötti sorszámokkal azonosítjuk.
A standard bemenet első sora a városok $N$ számát és az autópályák $M$ számát, illetve $A$ és $B$ sorszámát tartalmazza. A következő $M$ sor egy-egy autópályát ír le, vagyis három egész számot tartalmaz szóközzel elválasztva: a két végpont sorszámát $\left(x_i\mathrm{,}{y}_i\right)$, illetve az adott autópálya megtételéhez szükséges időt ($z_i$-t) tartalmazza. Az A városból a B városba mindenképp el lehet jutni egy vagy több autópályán végighaladva. A standard kimenet első sorába írjuk ki, hogy maximum mennyivel csökkenthető az utazási idő A és B között, a második sorba pedig annak a két városnak sorszámát, amelyek között az új vonalat építeni kell.