#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0

int *pripadnost, brCvorova, brVeza, trenutna, brUvrstenih, *uvrsteneVeze;
double *provizije, cenaPoKm, suma;

typedef struct {
	int u;
	int v;
	double udaljenost;
	double cena;
} Veza;

Veza *veze;

void promeniPripadnost(int u, int v) {
	int i;
	int pom = pripadnost[v];
	for (i=0; i<brCvorova; i++) {
		if (pripadnost[i]==pom) {
			pripadnost[i] = pripadnost[u];
		}
	}
}

int main() {
	int i, j;
	scanf("%d%d", &brCvorova, &brVeza);
	pripadnost = (int *)malloc(brCvorova*sizeof(int));
	provizije = (double *)malloc(brCvorova*sizeof(double));
	uvrsteneVeze = (int *)malloc(brVeza*sizeof(int));
	veze = (Veza *)malloc(brVeza*sizeof(Veza));

	scanf("%lf",&cenaPoKm);

	for (i=0; i<brCvorova; i++) {
		pripadnost[i] = i;
		scanf("%lf", &provizije[i]);
	}

	for (i=0; i<brVeza; i++) {
		scanf("%d%d%lf", &veze[i].u, &veze[i].v, &veze[i].udaljenost);
		uvrsteneVeze[i] = FALSE;
		double polaPuta = veze[i].udaljenost/2;
		double provizijeU = provizije[veze[i].u];
		double provizijeV = provizije[veze[i].v];
		veze[i].cena = polaPuta*cenaPoKm*(2.0+provizijeU+provizijeV);
	}

	suma = 0;
	trenutna = 0;
	brUvrstenih = 0;

	//sortiranje veza

	for (i=0; i<brVeza-1; i++)
		for (j=i+1; j<brVeza; j++)
			if (veze[i].cena > veze[j].cena) {
				Veza pom=veze[i];
				veze[i] = veze[j];
				veze[j] = pom;
			}

	while (brUvrstenih<brCvorova-1) {
		if (pripadnost[veze[trenutna].u] != pripadnost[veze[trenutna].v]) {
			promeniPripadnost(veze[trenutna].u, veze[trenutna].v);
			suma += veze[trenutna].cena;
			brUvrstenih++;
			uvrsteneVeze[trenutna] = TRUE;
		}
		trenutna++;
	}

    printf("%lf.\n", suma);
    for (i=0; i<brVeza; i++) {
        if (uvrsteneVeze[i]) {
            printf("Deonica (%d,%d)\n", veze[i].u, veze[i].v);
        }
    }
    return 0;
}











