Ovi tocmai şi-a cumpărat maşină şi doreşte să facă o călătorie într-un alt oraş. Pentru că este şofer începător, el îşi planifică să mergă spre oraşul de destinaţie în mai multe zile trecând zilnic prin câte un oraş intermediar. Astfel, în fiecare zi va parcurge drumul direct de la un oraş X la un oraş Y, în Y se va odihni, urmând ca următoarea zi să parcurgă o nouă etapă din traseu în acelaşi mod. Ovi s-a uitat pe hartă, unde identifică N oraşe numerotate de la 1 la N şi află astfel între ce oraşe sunt şosele (bidirecţionale) şi care este lungimea acestor şosele. Nu-l interesează să ajungă la destinaţie parcurgând un traseu de lungime minimă, nici în cât mai puţine zile, ci ca distanţa maximă parcursă zilnic să fie cât mai mică. Deci dacă traseul îl parcurge în k zile, iar distanţele parcurse zilnic sunt d1, d2, ..., dk, notând cu dmax valoarea maximă din acest şir, Ovi doreşte ca valoarea dmax să fie cât mai mică posibil.
Cerinţă
Scrieţi un program prin care să-l ajutaţi pe Ovi ca plecând din oraşul natal să ajungă în oraşul de destinaţie în una sau mai multe etape, iar distanţa dmax să fie minimă.
Date de intrare
Fişierul de intrare traseu1.in conţine pe prima linie numărul natural N reprezentând numărul de oraşe. Pe linia a doua se află numărul natural M reprezentând numărul de şosele bidirecţionale de pe hartă. Pe următoarele M linii se află câte 3 numere naturale separate prin spaţiu X, Y, D cu semnificaţia: există şosea bidirecţională între oraşele X şi Y de lungime D (X şi Y sunt oraşe diferite). Pe ultima linie se găsesc două numere naturale S şi F, unde S este oraşul de plecare, iar F este oraşul destinaţie.
Date de ieşire
Fişierul de ieşire traseu1.out va conţine o singură linie pe care va fi scris un singur număr reprezentând distanţa dmax dintre două oraşe de pe traseu, minimă posibil.
Restricţii
2 <= N <= 500
2 <= M <= 50 000
Distanţele dintre oraşe sunt numere naturale cuprinse între 1 şi 10 000
Va exista întotdeauna cel puţin un traseu de la oraşul de plecare la destinaţie
Traseul optim de la oraşul 1 la 7 care îndeplineşte cerinţele este 1-3-5-6-7, deoarece distanţa maximă dmax pe care este nevoit să o parcurgă într-o zi este 50 (între oraşele 3 şi 5).
Mai există şi alte trasee care nu sunt optime, de exemplu:
1-7 : distanţa dmax este 100
1-2-4-5-7 : distanţa dmax este 70
1-3-5-7 : distanţa dmax este 60