#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define up(i,j,k,l) for(int i=j;i<=k;i+=l)
#define down(i,j,k,l) for(int i=j;i>=k;i-=l)
using namespace std;
const int N=1e5+10;
int n,m,c;
vector<pair<int,int>> vc[N];
int a,b;
int d[N];
bool f[N];
queue<int> q;
void spfa()
{
	//O(n+m)
	memset(d,0x3f3f3f,sizeof d);
	q.push(a);
	d[a]=0;
	f[a]=true;
	int u;
	while(!q.empty()){
		u=q.front();
		q.pop();
		f[u]=false;
		for(pair<int,int> fw:vc[u]){
			if(d[fw.first]>d[u]+fw.second || d[fw.first]>d[u]+c*(u^fw.first)){
				if(d[fw.first]>d[u]+fw.second){
					d[fw.first]=d[u]+fw.second;
				}
				if(d[fw.first]>d[u]+c*(u^fw.first)){
					d[fw.first]=d[u]+c*(u^fw.first);
				}
				if(f[fw.first]==false){
					f[fw.first]=true;
					q.push(fw.first);
				}
			}
		}
		if(d[b]==0){
			return;
		}
	}
	return;
}
void solve()
{
	cin>>n>>m>>c;
	int u,v,w;
	//O(n)
	up(i,1,m,1){
		cin>>u>>v>>w;
		vc[u].push_back({v,w});
	}
	//O(n log2 n)
	up(i,0,n,1){
		for(int j=1;j<=n;j<<=1){
			if((i^j)<=n){
				vc[i].push_back({i^j,c*j});
			}
		}
	}
	cin>>a>>b;
	spfa();
	cout<<d[b];
	return;
}
int main()
{
    ios::sync_with_stdio(false);
	cin.tie(0);
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int _=1;
	//cin>>_;
	up(i,1,_,1){
		solve();
	}
	return 0;
}