#include <cstdio>

#include <algorithm>

#include <cstring>

#include <queue>

#define N 100004

#define M 4000000

#define inf 10000000000000

#define ll long long

#define setIO(s) freopen(s".in","r",stdin)

using namespace std;

struct Node

{

    int u;

    ll dis;

    Node(int u=0,ll dis=0):u(u),dis(dis){}

    bool operator<(Node b)const

    {

        return b.dis<dis;

    }

};

priority_queue<Node>q;

int n,m,C,edges,s,t;

ll d[N];

int hd[N],nex[M],to[M],val[M],done[N];

inline void addedge(int u,int v,int c)

{

    nex[++edges]=hd[u],hd[u]=edges,to[edges]=v,val[edges]=c;

}

inline void Dijkstra()

{

    int i,u,v;

    for(i=0;i<=n;++i) d[i]=inf;

    d[s]=0, q.push(Node(s,0));

    while(!q.empty())

    {

        Node e=q.top(); u=e.u,q.pop();

        if(done[u]) continue;

        done[u]=1;

        for(i=hd[u];i;i=nex[i])

            if(d[to[i]]>d[u]+val[i])

                d[to[i]]=d[u]+val[i],q.push(Node(to[i],d[to[i]]));

    }

}

int main()

{

    int i,j;

    // setIO("input");

    scanf("%d%d%d",&n,&m,&C);

    for(i=1;i<=m;++i)

    {

        int u,v,c;

        scanf("%d%d%d",&u,&v,&c), addedge(u,v,c);

    }

    for(i=0;i<=n;++i)

    {

        int l;

        for(l=0;(1<<l)<=n;++l) if((i^(1<<l))<=n)addedge(i,i^(1<<l),(1<<l)*C);

    }

    scanf("%d%d",&s,&t),Dijkstra(),printf("%lld\n",d[t]);

    return 0;

}