Server#10456
Amin e Murad hanno deciso di creare un server di gioco "Minecraft".
Per l'inaugurazione ufficiale del server hanno invitato ospiti. Gli ospiti vivono in città diverse e, collegandosi al server (a seconda della loro posizione), subiranno un certo ritardo (ping). Resisi conto delle possibili difficoltà, Amin e Murad hanno deciso di scegliere il luogo più ottimale per posizionare il server.
Ci sono città, numerate da a , e canali di comunicazione bidirezionali tra di esse. Il collegamento al server è possibile solo tramite questi canali. Con il loro aiuto è possibile stabilire una connessione tra due città qualsiasi. Allo stesso tempo, tra due città può esserci al massimo un canale di comunicazione diretto, e nessuna città è collegata a sé stessa tramite un canale. Per ogni canale è indicato il ritardo di trasmissione w_i.
Il ritardo di connessione tra una città qualsiasi e il server è considerato la somma minima possibile dei ritardi lungo i canali sul percorso da questa città al server.
Amin e Murad vogliono scegliere una città per posizionare il server in modo che il ritardo totale delle connessioni di tutti gli ospiti sia minimo. Se il server è posizionato nella stessa città in cui vive un ospite, il ritardo per quest'ultimo è considerato pari a zero.
Se esistono più città con lo stesso ritardo totale minimo, Amin e Murad sceglieranno la città con il numero più piccolo.
Determinate in quale città sarà posizionato il server e qual è il ritardo totale delle connessioni di tutti gli ospiti al server.
Nella prima riga sono dati tre numeri interi n~(1 \le n \le 10^4), m~(1 \le m \le 4 * 10^4), k~(1 \le k \le 100) — il numero di città, il numero di canali di comunicazione e il numero di ospiti rispettivamente. Nella seconda riga sono scritti numeri distinti c_i~(1 \le c_i \le n) — i numeri delle città in cui vivono gli ospiti.
In ciascuna delle successive righe sono dati tre numeri interi u_i, v_i, w_i~(1 \le u_i, v_i \le n) — la descrizione di un canale di comunicazione bidirezionale tra le città u_i e v_i con ritardo w_i~(1 \le w_i \le 10^4).
Stampate due numeri interi — il numero della città in cui sarà posizionato il server e il ritardo totale delle connessioni di tutti gli ospiti a questo server.
Esempio 1