Farmer John так ленив, что не хочет поддерживать пути ко всем $N$ пастбищам ($5\le N\le10{,}000$), номера $1\ldots N$. Каждое — дом одной коровы. Он удалит максимум из $P$ путей ($N-1\le P\le100{,}000$), сохранив связность. Определите оставшиеся $N-1$.

Двусторонний путь $j$ соединяет $S_j,E_j$ ($1\le S_j\le N;1\le E_j\le N;S_j\ne E_j$), требует время $L_j$ ($0\le L_j\le1{,}000$). Между парой не более одного прямого пути.

Коровы грустят из-за сокращения транспорта. Ежедневно посетите каждую хотя бы раз. При каждом визите в $i$, даже проходя мимо, говорите с ней время $C_i$ ($1\le C_i\le1{,}000$).

Пока коровы не перестанут грустить, ночуйте в одном выбранном пастбище. С его коровой говорите хотя бы утром после пробуждения и вечером после возвращения ко сну.

Если FJ оставляет предложенные пути и место сна оптимально, найдите минимальное время ежедневного посещения каждой коровы хотя бы раз.

Для первых $10$ посылок предоставят результаты на части настоящих тестов.

Входные данные

• Строка $1$: целые $N,P$ через пробел.

• Строки $2\ldots N+1$: строка $i+1$ содержит целое $C_i$.

• Строки $N+2\ldots N+P+1$: строка $N+j+1$ содержит целые $S_j,E_j,L_j$ через пробел.

Выходные данные

• Строка $1$: целое, полное время посещений, включая два визита к корове места сна.

Примеры

Входные данные 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

Выходные данные 1

176

Примечание

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

Оставьте эти пути:

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

Проснитесь в $4$ и пройдите $4,5,4,2,3,2,1,2,4$ за $176$ времени перед сном.

Подзадачи

Баллы: $300$

Авторы задачи: David Benjamin и Jacob Steinhardt, 2008