Odśnieżanie

Limit pamięci: 64 MB

Biednemu zawsze wiatr w oczy. Niedźwiedź (główny bohater zadania Niedźwiedź) bardzo ucieszył się, że nadeszła wczesna zima i już nie będzie musiał przemykać po lesie, cały czas brodząc po kolana w błocie i bacząc na czyhające na niego owady. Niestety, zima postanowiła uprzykrzyć życie Niedźwiedzia i śniegu nasypało tyle, że nasz bohater ledwo może się przemieszczać po lesie.

Niedźwiedź postanowił nie poddawać się i odśnieżyć las, a przynajmniej ścieżki prowadzące do trzech polan, koło których zazwyczaj łapie on ryby na kolację. Las składa się z polan połączonych (dwukierunkowymi) ścieżkami. Polany są ponumerowane liczbami od do . Wygląda na to, że niektóre ścieżki mogą biec tunelami lub estakadami, co nieco zdziwiło Niedźwiedzia, ale ma on teraz poważniejsze problemy na głowie. Dla każdej ścieżki Niedźwiedź wie, ile czasu będzie potrzebować na jej odśnieżenie.

Ile czasu będzie on musiał spędzić na odśnieżenie tylu ścieżek, by mógł poruszać się między swoją norą (położoną obok polany numer ), a polanami, koło których łapie ryby, chodząc jedynie po odśnieżonych ścieżkach?

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite i (, ). Oznaczają one kolejno liczbę polan w lesie oraz liczbę łączących je ścieżek. Drugi wiersz zawiera trzy różne od siebie liczby całkowite () – są to numery polan, przy których Niedźwiedź łapie ryby. Każdy z kolejnych wierszy opisuje jedną ścieżkę. W -tym z tych wierszy znajdują się trzy liczby całkowite (, , ). Oznaczają one, że polany o numerach i są połączone dwukierunkową ścieżką, której odśnieżenie zajmie sekund. Każda para polan może być połączona co najwyżej jedną ścieżką. Pomiędzy każdą parą polan ze zbioru można przejść, idąc po ścieżkach.

Wyjście

Na wyjściu należy wypisać minimalną liczbę sekund potrzebną do odśnieżenia ścieżek, które umożliwią poruszanie się między polanami numer , , i .

Przykład

Dla danych wejściowych:

7 8
3 6 7
1 2 2
1 4 3
2 3 4
3 5 3
3 7 5
4 5 3
4 6 5
5 7 4

poprawną odpowiedzią jest:

18

Ograniczenia

W testach wartych co najmniej punktów zachodzi oraz .

Autor zadania: Marcin Mucha.