Farmer John descubrió el secreto de la mantequilla más dulce de Wisconsin: azúcar. Al poner un terrón en los pastos, sabe que las $N$ vacas ($1\le N\le500$) lo lamerán y producirán mantequilla muy dulce que venderá más cara. Gasta el dinero extra en lujos para ellas.

FJ es astuto. Como Pavlov antaño, sabe entrenarlas para ir a cierto pasto al oír una campana. Pondrá allí el azúcar y tocará la campana a media tarde para obtener leche perfecta en el ordeño nocturno.

Cada vaca pasa el tiempo en un pasto dado, no necesariamente sola. Con sus ubicaciones y los caminos, encuentra dónde poner el azúcar para minimizar la distancia total recorrida al oír la campana. La conexión de los campos garantiza siempre una solución.

Entrada

• Línea $1$: enteros separados por espacios, vacas $N$, pastos $P$ ($2\le P\le800$), caminos $C$ ($1\le C\le1{,}450$). Números únicos $1\ldots N$ para vacas y $1\ldots P$ para pastos.

• Líneas $2\ldots N+1$: entero, pasto de una vaca; la $i$ está en la línea $i+1$.

• Líneas $N+2\ldots N+C+1$: tres enteros separados por espacios, dos pastos y una longitud. Caminos bidireccionales, como máximo uno directo por pareja. Primeros dos en $1\ldots P$, tercero en $1\ldots225$.

Salida

• Línea $1$: entero, distancia total mínima de las vacas hasta el pasto con azúcar.

Ejemplos

Entrada 1

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

Salida 1

8

Nota

El diagrama muestra geométricamente las conexiones:

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

Poner el azúcar en $4$ hace caminar $3$ unidades a la vaca $1$, $5$ a la $2$ y $0$ a la $3$, total $8$.

Autor del problema: Greg Galperin, 2001