#include <bits/stdc++.h>
using namespace std;

const int inf = INT_MAX/3;
int n, m, c, a, b;

struct edge {
    int w, v;
};

struct node {
    int dis, u;

    bool operator>(const node &rhs) const {
        return dis > rhs.dis;
    }
};

vector<vector<edge>> adj;
vector<int> dist;
vector<bool> vis;

void dijkstra() {
    priority_queue<node, vector<node>, greater<>> q;
    q.push({0, a});
    dist[a] = 0;

    while (!q.empty()) {
        int du = q.top().dis, u = q.top().u;
        q.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (auto [w, v]: adj[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                q.push({dist[v], v});
            }
        }
        for (int j = 1; j <= n; j = 2 * j) {
            int v = u ^ j, w = j * c;
            if (1 <= v && v <= n && dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                q.push({dist[v], v});
            }
        }
    }
}

int main() {
    cin >> n >> m >> c;
    adj.resize(n + 1);
    dist.resize(n + 1, inf);
    vis.resize(n + 1);
    for (int i = 0; i < m; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        adj[x].push_back({z, y});
    }

    cin >> a >> b;
    dijkstra();
    cout << dist[b] << "\n";


    return 0;
}