#include <bits/stdc++.h>
#define lowbit(i) (x&(-x))
using namespace std;
const int N=2e5+15;
int n,m,c,vis[N],dis[N],x,y,z,A,B;
inline int read(){
	int w=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while('0'<=ch&&ch<='9'){
		w=w*10+ch-'0';
		ch=getchar();
	}
	return w*f;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
struct Point{
	int p,w;
	bool operator < ( const Point &b) const&
	{
		return w>b.w;
	}
};
struct Edge{
	int v,w;
};
vector <Edge> e[N];
priority_queue <Point> q;
void Dijkstra(){
	memset(dis,0x3f,sizeof(dis));
	q.push(Point{A,0});
	dis[A]=0;
	while(!q.empty()){
		Point now=q.top();
		q.pop();
		if(vis[now.p]){
			continue;
		}
		int u=now.p,len=e[u].size();
		vis[u]=1;
		for(int i = 0 ; i<len ; i++){
			int to=e[u][i].v,w=e[u][i].w;
			if(dis[u]+w<dis[to]){
				dis[to]=dis[u]+w;
				q.push({to,dis[to]});
			}
		}
	}
}
void add(int x){
	for(int i = 1 ; i<=n ; i<<=1){
		e[x].push_back({i,(x^i)*c});
		e[i].push_back({x,(x^i)*c});
	}
}
int main(){
	n=read(),m=read(),c=read();
	for(int i = 1 ; i<=m ; i++){
		x=read(),y=read(),z=read();
		e[x].push_back({y,z});
	}
	for(int i = 1 ; i<=n ; i++)
	add(i);
	A=read(),B=read();
	Dijkstra();
	write(dis[B]);
	return 0;
}