仔细观察：如果两个数在二进制上有超过一处的不同处，那么我们就可以用经过多条边代替直接走到，并且花费不变。

#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];
priority_queue< pair<int,int> ,vector< pair<int,int> >,greater< pair<int,int> > > q;
void dij()
{
	memset(d,0x3f3f3f,sizeof d);
	d[a]=0;
	int u;
	q.push({0,a});
	while(!q.empty()){
		u=q.top().second;
		q.pop();
		if(f[u]==true){
			continue;
		}
		f[u]=true;
		for(auto fw:vc[u]){
			if(d[fw.first]>d[u]+fw.second){
				d[fw.first]=d[u]+fw.second;
				q.push({d[fw.first],fw.first});
			}
		}
	}
	return;
}
void solve()
{
	cin>>n>>m>>c;
	int u,v,w;
	up(i,1,m,1){
		cin>>u>>v>>w;
		vc[u].push_back({v,w});
	}
	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;
	dij();
	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;
}