Se da un graf orientat cu n noduri si m muchii ponderate (costuri pozitive). Determinati diametrul ponderat al grafului, adica cea mai mare distanta minima dintre orice doua noduri accesibile intre ele.
- Date de intrare
- Pe prima linie se citesc n si m. Urmeaza m linii, fiecare cu trei numere x y c, reprezentand o muchie orientata de la x catre y cu costul c.
- Date de iesire
- Se afiseaza diametrul ponderat al grafului (0 daca n = 1 sau nu exista nicio pereche accesibila).
- Restrictii
- 1 <= n <= 200, 0 <= m <= n*(n-1), 1 <= c <= 1000
Exemple
Exemplul 1
Intrare
4 3 1 2 3 2 3 4 3 4 2
Iesire
9
Exemplul 2
Intrare
1 0
Iesire
0