In caso di invasione, per favore...#9886
Dopo che il rover Curiosity ha scoperto su Marte non solo acqua, ma anche una banda di alieni aggressivi e assetati di sangue, il comune di Louvain-la-Neuve ha deciso di prendere precauzioni: sono stati costruiti rifugi in grado di ospitare tutti gli abitanti della città in caso di attacco alieno.
In tutta la città sono stati eretti diversi rifugi a prova di alieno, nei quali i cittadini potranno attendere che l'invasione finisca. Tuttavia, a causa delle normative comunali e dei codici edilizi locali, la dimensione dei rifugi è limitata. Pertanto le autorità devono assegnare a ciascun abitante un rifugio verso cui dirigersi con calma, qualora un giorno una flotta di UFO dovesse oscurare il sole. In nessun rifugio può essere inviato più gente di quanta ne possa contenere e, rispettando questa condizione, è fondamentale minimizzare il tempo impiegato da tutti per raggiungere i rifugi.
Rappresentiamo Louvain-la-Neuve come una rete di località collegate da strade bidirezionali. I rifugi si trovano in punti della città, e per ciascuno di essi è data la capacità massima. In quanto tempo minimo tutti gli abitanti potranno raggiungere i rifugi, se vengono distribuiti tra i rifugi in modo ottimale?
Il comune di Louvain-la-Neuve si è assicurato che la capacità totale dei rifugi sia sufficiente per tutti gli abitanti e che ogni rifugio sia raggiungibile da qualsiasi località. Pertanto è sempre possibile mettere al riparo tutti.
Nella prima riga sono dati tre numeri interi: il numero di località n~(1 \le n \le 10^5), il numero di strade m~(0 \le m \le 2 \cdot 10^5) e il numero di rifugi s~(1 \le s \le 10).
Nella seconda riga sono dati numeri interi p_1, p_2, \dots, p_n~(0 \le p_i \le 10^9), dove p_i — è il numero di persone che vivono nella località .
Ciascuna delle successive righe contiene tre numeri interi , e w~(1 \le u, v \le n, 1 \le w \le 10^9). Ciò significa che le località e sono collegate da una strada bidirezionale, il cui attraversamento richiede un tempo . Due qualsiasi località sono collegate direttamente da non più di una strada, e nessuna strada collega una località con se stessa.
Ciascuna delle ultime righe contiene due numeri interi s_i e c_i~(1 \le s_i \le n, 1 \le c_i \le 10^9). Ciò significa che nella località s_i si trova un rifugio di capacità c_i.
Stampate il tempo minimo necessario per mettere al riparo tutti gli abitanti.
Esempio 1
Esempio 2
Esempio 3
Esempio 4