#include<bits/stdc++.h>
using namespace std;
long long  n,m,c;
struct code{
	long long to,num;
};
vector<code>q[100001];
long long f,T,v,dp[100001];
queue<long long>pp;
long long A,B;
int main(){
	cin>>n>>m>>c;
    memset(dp,30,sizeof(dp));
	for(long long i=1;i<=n;i++){
		for(long long o=0;o<=20;o++){
        	int qwq = i ^ (1 << o); 
			if (qwq > n)continue; 
			if(o==i)continue;
			q[i].push_back(code{1<<o,qwq*c});
		    q[1<<o].push_back(code{i,qwq*c});
		}
	}
	for(long long o=1;o<=m;o++){
		cin>>f>>T>>v;
		q[f].push_back(code{T,v});
	}
	cin>>A>>B;
	pp.push(A);
    dp[A]=0;
	while(!pp.empty()){
		long long kl=pp.front();pp.pop();
		for(code i:q[kl]){
			if(dp[i.to]>dp[kl]+i.num){
				dp[i.to]=dp[kl]+i.num;
				pp.push(i.to);
			}
		}
	}
	cout<<dp[B];
	return 0;
}