Pukanus

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 1111;
const int M = 11111;
const int INF = (int)1e9;

vector<int> 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;
}