Farmer John jest zbyt leniwy, by utrzymywać ścieżki do wszystkich $N$ pastwisk ($5\le N\le10{,}000$), numerowanych $1\ldots N$. Każde ma jedną krowę. Usunie jak najwięcej z $P$ ścieżek ($N-1\le P\le100{,}000$), zachowując spójność. Wybierz pozostałe $N-1$.

Dwukierunkowa ścieżka $j$ łączy $S_j,E_j$ ($1\le S_j\le N;1\le E_j\le N;S_j\ne E_j$), zajmuje $L_j$ czasu ($0\le L_j\le1{,}000$). Najwyżej jedna bezpośrednia na parę.

Krowy smucą się z powodu redukcji transportu. Odwiedzaj każdą co najmniej raz dziennie. Każda wizyta w $i$, nawet przejście, wymaga rozmowy przez $C_i$ ($1\le C_i\le1{,}000$).

Śpij każdej nocy na tym samym wybranym pastwisku aż się pocieszą. Z jego krową porozmawiasz przynajmniej po obudzeniu i wieczorem po powrocie do snu.

Jeśli FJ zachowa twoje ścieżki i wybierzesz optymalne miejsce snu, znajdź minimalny dzienny czas odwiedzenia każdej co najmniej raz.

Pierwsze $10$ zgłoszeń otrzyma wyniki na części prawdziwych testów.

Wejście

• Wiersz $1$: całkowite $N,P$ ze spacją.

• Wiersze $2\ldots N+1$: wiersz $i+1$, całkowite $C_i$.

• Wiersze $N+2\ldots N+P+1$: wiersz $N+j+1$, całkowite $S_j,E_j,L_j$ ze spacjami.

Wyjście

• Wiersz $1$: całkowity czas odwiedzin, włącznie z dwiema u krowy pastwiska snu.

Przykład

Wejście 1

5 7
10
10
20
6
30
1 2 5
2 3 5
2 4 12
3 4 17
2 5 15
3 5 6
4 5 12

Wyjście 1

176

Uwagi

              +-(15)-+
             /        \
            /          \
     1-(5)-2-(5)-3-(6)--5
            \   /(17)  /
         (12)\ /      /(12)
              4------+

Zachowaj te ścieżki:

     1-(5)-2-(5)-3      5
            \          /
         (12)\        /(12)
             *4------+

Obudź się w $4$, odwiedź $4,5,4,2,3,2,1,2,4$ i spędź $176$ przed snem.

Podzadania

Punkty: $300$

Autorzy zadania: David Benjamin i Jacob Steinhardt, 2008