#include<bits/stdc++.h>

using namespace std;

const int N=5*1e5+5;

struct node{
	int id,d;
	bool friend operator<(node a,node b){return a.d>b.d;}
};
struct edge{int t,w;};
priority_queue<node>q;
int n,m,a,b,c,dis[N];
vector<edge>G[N];
bool vis[N];

int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
	cin>>n>>m>>c;memset(dis,0x3f,sizeof(dis));
	for(int u,v,w;m--;)cin>>u>>v>>w,G[u].push_back({v,w});
	for(int i=0;i<=n;i++)
		for(int j=1;j<=n;j<<=1)
			G[i].push_back({i^j,j*c});
	cin>>a>>b,q.push({a,0});dis[a]=0;
	while(!q.empty()){
		node o=q.top();q.pop();
		if(!vis[o.id]){
			vis[o.id]=true;
			for(edge x:G[o.id])
				if(dis[o.id]+x.w<dis[x.t])
					dis[x.t]=dis[o.id]+x.w,q.push({x.t,dis[x.t]});
		}
	}
	return cout<<dis[b]<<endl,0;	
}