#include #include #include using namespace std; const int N = 1111; const int M = 11111; const int INF = (int)1e9; vector g[N]; int n, m, k, deg[N], x[N], y[N], S, T, c, ef[M], es[M], ev[M], d[M], used[M]; void add(int x, int y, int z) { es[++c] = y; ef[c] = x; ev[c] = z; g[x].push_back(c); es[++c] = x; ef[c] = y; ev[c] = z; g[y].push_back(c); ++deg[x]; ++deg[y]; } void input() { scanf("%d%d%d", &n, &m, &k); for (int i = 1; i <= n; ++i) { scanf("%d%d", &x[i], &y[i]); } for (int i = 0; i < m; ++i) { int x, y, z; scanf("%d%d%d", &x, &y, &z); add(x, y, z); } scanf("%d%d", &S, &T); } int triangleArea(int x1, int y1, int x2, int y2, int x3, int y3) { return (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1); } bool counterClockwise(int x1, int y1, int x2, int y2, int x3, int y3) { return triangleArea(x1, y1, x2, y2, x3, y3) > 0; } void dijkstra() { for (int i = 1; i <= c; ++i) { d[i] = INF; } for (int i = 0; i < g[S].size(); ++i) { int h = g[S][i]; int to = es[h]; int dist = ev[h]; if (counterClockwise(x[S], y[S] - 1, x[S], y[S], x[to], y[to])) { dist += deg[S] * k; } d[h] = min(d[h], dist); } for (;;) { int u = 0; for (int i = 1; i <= c; ++i) { if (!used[i] && (!u || d[i] < d[u])) { u = i; } } if (u == 0) { break; } used[u] = true; int from = ef[u], v = es[u]; for (int i = 0; i < g[v].size(); ++i) { int h = g[v][i]; int to = es[h]; int dist = ev[h]; if (counterClockwise(x[from], y[from], x[v], y[v], x[to], y[to]) || from == to) { dist += deg[v] * k; } if (dist + d[u] < d[h]) { d[h] = dist + d[u]; } } } } int main() { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); input(); dijkstra(); int res = INF; for (int i = 1; i <= c; ++i) { if (es[i] == T && d[i] < res) { res = d[i]; } } printf("%d\n", res); return 0; }