Farmer John открыл секрет самого сладкого масла в Wisconsin: сахар. Положив кусочек на пастбище, он знает, что $N$ коров ($1\le N\le500$) его оближут и дадут сверхсладкое масло, которое можно продать дороже. Дополнительные деньги, конечно, идут на роскошь для коров.

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

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

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

• Строка $1$: целые через пробел: число коров $N$, пастбищ $P$ ($2\le P\le800$), путей $C$ ($1\le C\le1{,}450$). Коровы имеют уникальные номера $1\ldots N$, пастбища $1\ldots P$.

• Строки $2\ldots N+1$: целое, номер пастбища коровы; корова $i$ в строке $i+1$.

• Строки $N+2\ldots N+C+1$: три целых через пробел — два пастбища и длина пути. Он двусторонний; пара не имеет более одного прямого пути. Первые числа в $1\ldots P$, третье в $1\ldots225$.

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

• Строка $1$: целое — минимальный суммарный путь коров до пастбища с сахаром.

Примеры

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

3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5

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

8

Примечание

Диаграмма геометрически показывает соединения:

          P2  
 P1 @--1--@ C1
     \    |\
      \   | \
       5  7  3
        \ |   \
         \|    \ C3
       C2 @--5--@
          P3    P4

В пастбище $4$ корова $1$ проходит $3$, корова $2$ — $5$, корова $3$ — $0$, всего $8$.

Автор задачи: Greg Galperin, 2001