Az ország N városa között különböző teherbírású utak vannak. Két város között árut szeretnénk szállítani a lehető legnagyobb kapacitású teherautóval olyan útvonalon, ahol az autó tehersúlya nem nagyobb, mint az egyes utak teherbírása. 

Írjunk programot, ami adott A és B városra megadja, hogy maximum mekkora tehersúlyú teherautó közlekedhet közöttük és merre kell menni!

A bemenet első sorában a városok száma (1 <= N <= 100), a köztük levő utak száma (1 <= M <= 10000), a kezdő és a cél város sorszáma (1 <= A ≠ B <= N) van, egy-egy szóközzel elválasztva. A következő M sor mindegyikében egy-egy út leírása található: azon két város sorszáma (1 <= sorszám <= N), amelyek között a kétirányú út vezet, valamint az út teherbírása (1 <= teherbírás <= 1000).

A kimeneti állományba 2 sort kell írni. Az elsőbe a maximális tehersúly kerüljön, a másodikba pedig az oda vezető úton levő városok sorszáma, egy-egy szóközzel elválasztva, az útvonal sorrendjében (azaz az első sorszám biztosan A, az utolsó sorszám biztosan B legyen)! Több megoldás esetén bármelyik megadható.

Bemenet	Kimenet
5 6 3 4 2 1 100 1 4 100 3 1 200 3 5 300 2 3 900 4 5 400	300 3 5 4

A feladat forrása: NTOITV 2012 3. forduló, 11-13. évfolyam

Algoritmusok: 

megoldás