Egy megye településeiről tudjuk, hogy bármely településről bármelyik másikra pontosan egy útvonalon lehet eljutni. Egy üzlethálózat minél több településen szeretne üzletet nyitni. Tudjuk, hogy melyik településen van a raktár, ahonnan az egyes üzletekbe szállítaná az árut. Ismerjük, hogy melyik településen mekkora hasznot fog hozni az üzlet, valamint hogy melyik út használatáért mekkora úthasználati díjat kell fizetni. Az összhaszon az üzletekben termelt haszonból levonva az úthasználati díjakat. 

Írjunk programot, ami kiszámítja, hogy mekkora az elérhető legnagyobb haszon és ehhez mely településeken kell üzletet nyitni!

A bemenet  első sorában a települések N száma (1 <= N <= 10000) és a raktáros település R sorszáma (1 <= R <= N) van. A második sor pontosan N egész számot tartalmaz (egy-egy szóközzel elválasztva), az i-edik szám az i. településem elérhető hasznot. A következő N-1 sorban három egész szám van (egy-egy szóközzel elválasztva): két település sorszám, amelyek között kétirányú út van, és az érte fizetendő úthasználati díj.

Az első sorbába azt az elérhető legnagyobb hasznot kell írni! A második sorba a megnyitandó üzletek M számát kell írni, a harmadikba M sorszámot, egy-egy szóközzel elválasztva: azon települések sorszámát, ahol üzletet nyitunk! A számok sorrendje közömbös. Több megoldás esetén bármelyik megadható.

Bemenet	Kimenet
10 2 100 100 50 50 50 100 200 100 50 50 1 2 200 3 4 10 4 5 10 4 2 100 2 6 10 6 7 100 6 8 150 8 9 30 10 8 60	320 6 2 3 4 5 6 7

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

Algoritmusok: 

megoldás