#include<queue>
#include<vector>
#include<iostream>
using namespace std;
const int N=2e5+5;
struct edge
{
	long long v,w;
	bool operator<(const edge &n) const
	{
		return n.w<w;	
	}	
};
long long n,m,c,u,v,w,s,t;
long long dis[N];
bool vis[N];
vector<edge> e[N];
priority_queue<edge> Q;
void dijkstra(long long s)
{
	for(long long i=1;i<=n;i++) dis[i]=1e18;
	dis[s]=0;
	Q.push({s,0});
	while(!Q.empty())
	{
		edge tq=Q.top();
		Q.pop();
		long long x=tq.v;
		if(vis[x]) continue;
		vis[x]=true;
		for(long long i=0;i<e[x].size();i++)
		{
			edge tt=e[x][i];
			long long v=tt.v,w=tt.w;
			if(vis[v]) continue; 
			if(dis[x]+w<dis[v])
			{
				dis[v]=dis[x]+w;
				Q.push({v,dis[v]});
			}
		}
	}
}
int main()
{
	cin>>n>>m>>c;
	for(long long i=0;i<=n;i++)
	{
		for(long long j=1;j<=n;j*=2)
		{
			if((i^j)>n) continue;
			e[i].push_back({i^j,j*c});	
		}	
	}
	for(long long i=1;i<=m;i++)
	{
		cin>>u>>v>>w;
		e[u].push_back({v,w});
	}
	cin>>s>>t;
	dijkstra(s);
	cout<<dis[t];
	return 0;
}