// 最短路+二进制优化建图 Dijkstra 算法 O(MlogN)
#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;

const int N=1e5+5,M=22e5;
int h[N],to[M],ww[M],ne[M],idx;
void add(int a,int b,int c){
  to[++idx]=b,ww[idx]=c,ne[idx]=h[a],h[a]=idx;
}
int n,m,c,s,t;
int d[N];bool vis[N];

void dijkstra(){
  memset(d,0x3f,sizeof d);d[s]=0;
  priority_queue<pii,vector<pii>,greater<pii> > q;
  q.push({0,s});
  while(!q.empty()){
    int u=q.top().second;q.pop();
    if(vis[u]) continue;vis[u]=1;
    for(int i=h[u];i;i=ne[i]){
      int v=to[i],w=ww[i];
      if(d[v]>d[u]+w){
        d[v]=d[u]+w;
        q.push({d[v],v});
      }
    }
  }
}
int main(){
  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  cin>>n>>m>>c;
  for(int i=1,a,b,c;i<=m;i++)cin>>a>>b>>c,add(a,b,c);
  for(int i=0;i<=n;i++)for(int k=0;k<=20;k++)
    if((i^(1<<k))<=n) add(i,i^(1<<k),(1<<k)*c);
    
  cin>>s>>t;
  dijkstra();
  cout<<d[t];
}