Animando las Vacas.


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 32M

Author:
Problem types
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, Swift, VB

El Granjero Juan se ha vuelto tan perezoso que no quiere continuar manteniendo los senderos vacunos que actualmente le dan una manera de visitar cada uno de sus N (5 \leq N \leq 10,000) pastizales (convenientemente numerados 1..N). Cada uno de los pastizales es el hogar de una vaca. GJ planea quitar tantos de los P (N-1 \leq P \leq 100,000) caminos como sea posible mientras se mantengan conectados los pastizales. Usted debe determinar con cuáles N-1 senderos quedarse.

El sendero bidireccional j conecta los pastizales S_j y E_j (1 \leq S_j \leq N; 1 \leq E_j \leq N; S_j \neq E_j) y requiere L_j (0 \leq L_j \leq 1,000) tiempo para recorrerse. Ningún par de pastizales está conectado por más de un camino.

Las vacas están tristes de que su sistema de transporte esté siendo reducido. Usted debe visitar cada vaca al menos un día para animarla. Cada vez que usted visita el pastizal i (aún si usted está de paso), usted debe hablarle a la vaca por tiempo C_i (1 \leq C_i \leq 1,000).

Usted pasara cada noche en el mismo pastizal (el cuál usted elegirá) hasta que las vacas se hayan recuperado de su tristeza. Usted terminará hablando con la vaca en el pastizal dormitorio al menos en la mañana cuando usted se levante y en la noche cuando usted haya vuelto a dormir.

Asumiendo que el Granjero Juan siga su sugerencia de cuales senderos dejar y usted elija el pastizal óptimo donde dormir, determine el tiempo mínimo que le tomará visitar cada vaca al menos una vez en un día.

Para sus primeros 10 envíos, a usted se le dará los resultados de correr su programa con una parte de los datos reales de prueba.

Entrada

  • Línea 1: Dos enteros separados por un espacio: N y P
  • Líneas 2..N+1: La línea i+1 contiene un solo entero: C_i
  • Líneas N+2..N+P+1: La línea N+j+1 contiene tres enteros separados por espacios: S_j, E_j, y L_j.

Ejemplo de Entrada

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

Detalles de la Entrada

Salida

Un solo entero, el tiempo total que toma visitar todas las vacas (incluyendo las dos visitas a las vaca en su pastizal dormitorio).

Ejemplo de Salida

176

Detalles de la Salida

Mantenga estos caminos:

Levántese en el pastizal 4 y visite los pastizales en el orden 4, 5, 4, 2, 3, 2, 1, 2, 4 gastando un tiempo total de 176 antes de volver a dormir.


Comments


  • -5
    Primervirgen  commented on Aug. 4, 2019, 6:08 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 6
      Leonardo  commented on Aug. 15, 2019, 3:38 a.m.

      Si