#include <iostream>
#include <vector>
using namespace std;
//Рекомендация: чтение лучше начать с функции "main"
int n,m,b,c;//Переменные из условия

struct boil{//Структура, описывающая котлы и их взаимодействие
	int mass=0;//Масса топлива имеется ввиду
	int number=0;//Порядковый номер при инициализации (для удобства оперирования структурой)
	vector<boil*> address;//Сюда записываем котлы, которые связаны с данным
	vector<int> distance;//Сюда- расстояние между ними.
};

int empty=0;//Порядковый номер котла, в котором недостаёт топлива
int near_tube=0;//Номер трубы, из которой будет перекачиваться топливо в нужный котёл
vector<int> visit;//Вектор, в котором отмечаются посещённые котлы
			//Комментарии с тестовым выводом оставлены специально. При понимании кода может помочь некая визуализация, достаточно лишь убрать "//" (см. "!")
int Min_way(boil* A, int i, int from){
	//cout<<from+1<<"->"<<A[i].number+1<<"-->";//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

	
	if(A[i].mass>b){//Сугубо для рекурсии. В случае, если программа нашла котёл, откуда можно перкачать
		near_tube=A[i].number;
		return 0;//Расстояние до этого котла потом учтётся
	}

	int min=0;//Индекс в векторе адресов/длин ближайшего вектора
	
	bool t=0;//Найдётся ли такой котёл, удовлетворяющий условиям ниже?
	for(int j=0; j< A[i].distance.size(); j++){
		bool t2=true,t1=true;//просто флаги
		for(int u=0; u<visit.size();u++){//Проверяем, не проверялся ли уже этот вектор
			if(visit[u]==A[i].address[j]->number) t2=false;
			if(visit[u]==A[i].address[min]->number)t1=false;//Для максимально корректного выбора минимума
		}
		if(A[i].address[j]->number==empty || A[i].address[j]->number==from)t2=false;//Чтобы избежать зацикливания
		if(A[i].address[min]->number==empty ||  A[i].address[min]->number==from)t1=false;
		
		if(A[i].distance[min]>=A[i].distance[j] && t2 || !t1 && t2){//Минимальный из всех вариантов. Либо какой-то вместо некорректного прошлого
			min=j;
			t=1;//Да, такой котёл есть
		}
	}
	
	if(t==0){//Если котёл в векторе адресов один, то t==0 в любом случае. Дополнительная проверка
		if(A[i].distance.size()==1){
			if(A[i].address[0]->mass>b){
				near_tube=A[i].address[0]->number;
				return A[i].distance[0];
			}
			else{
				return -1;//Эта ветка не приводит к котлу с топливом.
			}
		}
		else return -1;
	}
	else if(A[i].address[min]->mass==b){//Если самый близкий котёл имеет минимум топлива. Нужно проверить, какой котёл с топливом (если такой есть) ближе всех к этому уже
		visit.push_back(A[i].number);//Отмечаем, что этот котёл был посещён. В остальных случаях это не требуется, так как там либо в котёл с топливом уходит ветка,
		//либо становится понятно, что ветка тупиковая
		
		bool t1=true;
		long long min2=-1;//Собственно, путь уже от этого котла, до ближайшего с топливом
		
		for(int k=0; k<visit.size() && t1; k++){//Проверка, посещали ли
			if(visit[k]==A[i].address[min]->number)t1=false;
		}
		if(A[i].address[min]->number==from)t1=false;
		
		if(t1)	min2=Min_way(A,A[i].address[min]->number,A[i].number);//Вызов самой фунции
		if(min2>=0)min2+=A[i].distance[min];//Если ветка не тупиковая (min2!=-1), то добавляем расстояние до данного котла (от котла для которого первоначально вызывалась фунцкия)
		
	//	cout<<"("<<min2<<")";//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
		
		int n1=near_tube;//Запоминает значение near_tube, так как сама near_tube изменяется с каждым вызовом функции, и не всегда следующее значение правильное
		
		for(int j=0; j<A[i].distance.size(); j++){//Перебераем все варианты 
			if(j!=min && A[i].address[j]->mass>=b && A[i].address[j]->number!=from){//Эти случаи уже рассматривали
				visit.push_back(A[i].number);//При вызове min2 фунция могла пройти и этот момент и дойти до обнуления visit, поэтому нужно отметить посещение ещё раз. 
				long long a=0;//Значение от рассматриваемой трубы
				bool t3=true;
				for(int k=0; k<visit.size() && t3; k++){//Проверка на посещение
					if(visit[k]==A[i].address[j]->number)t3=false;
				}
				
				if(A[i].address[j]->number==A[empty].number)t3=false;
				
				
				if(t1 && t3){//Если не были, проеряем
					a=Min_way(A,A[i].address[j]->number,A[i].number);
				}
				else return-1;
				if(a>=0)a+=A[i].distance[j];//Не тупиковая ветка- добавляем расстояние
				
			//	cout<<"("<<a<<")";//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
				
				if(a>=0 && min2>=a && A[near_tube].mass>b ||min2<0){//Нахождение, собственно, самого близкого из котлов, где есть топливо. Тупиковые пропускаются
				//Если минимум сам не ведёт к подходящему котлу, то подходят любые другие пути, которые ведут
					min2=a;
					n1=near_tube;
				}
				visit.clear();// обнуляем вектор для следующего витка цикла
			}
		}
		near_tube=n1;//возвращаем нужное значение
		return min2;//возвращаем значение функции
	}
	else if(A[i].address[min]->mass<b){
		return -1;
	}
	else{
		near_tube= A[i].address[min]->number;
		return A[i].distance[min];
	}
}

int main() {//Ввод данных
	cin>>n>>m>>b>>c;
	boil A[n];
	for(int i=0; i<n; i++){
		int a;
		cin>>a;
		A[i].mass=a;
		A[i].number=i;
		if(A[empty].mass>a)empty=i;
	}
	
	int d,k,g;
	while(cin>>d>>k>>g){//Да, возможно тут было бы логичнее "for", но один тест упорно не хотел проходиться с ним, так что пришлось оставить "while"
			A[d-1].address.push_back(&A[k-1]);//см. структуру "boil"
			A[k-1].address.push_back(&A[d-1]);
			A[k-1].distance.push_back(g);
			A[d-1].distance.push_back(g);
	}//Таким образом порядковый номер близлежащего котла в "address" будет совпадать с расстоянием между этим котлом и тем, в чей вектор структуры записывается (distance)

	unsigned long long s=0;
	while(A[empty].mass<b){//Пока, собственно, котёл не заполнится
	/*	for(int i=0; i<n;i++){//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
			cout<<A[i].mass<<" ";
		}cout<<endl;*/
		
		unsigned long long a=Min_way(A,A[empty].number, A[empty].number);//Вызываем функцию, которая находит минимальное расстояние от нужного котла до того, в котором есть топливо
		//В том числе, с перекачкой через другие котлы
		if(A[near_tube].mass-b+A[empty].mass<b){//Если даже после перекачки в котле всё ещё не будет хватать топлива
			A[empty].mass+=A[near_tube].mass-b;
			s+=a*(A[near_tube].mass-b);
			A[near_tube].mass=b;
		}
		else{
			int tmp=b-A[empty].mass;
			A[near_tube].mass-=tmp;//Да, это уже не влияет на дальнейшее решение. Просто мне показалось правильнее, чтобы программа заканчивала работу с реальным количеством топлива в котлах
			A[empty].mass=b;
			s+=a*tmp;
		}
		//cout<<"   : "<<a<<" "<<A[empty].mass<<" "<<near_tube<<endl<<endl;//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
	}

	cout<<s*c;//Вывод ответа
	return 0;
}