Copogonia

Copogonia is a country with a set of $n$ cities, which currently has $n$ roads. The roads form a convex polygon, hence the name of the country. There are always exactly two ways to travel between any pair of distinct cities (clockwise or counter-clockwise). For some pairs, even the shorter of the two routes takes too long.

A survey found that citizens are happy only if no route between any two cities has length greater than $m$. In other words, the path between any two cities must have length $m$ or less.

The government may build up to $k$ new roads. Each new road connects two cities that are not already directly connected, and its length must equal the straight-line distance between those two cities. Each road has a construction cost. Find the minimum total cost of a subset of roads that keeps all citizens happy.

The first line contains three integers $n$, $k$, and $m$ ($4 \le n \le 50$, $1 \le k \le 10$, $m$ is the maximum allowed travel distance). Each of the next $n$ lines contains two integers $x_i$ and $y_i$ ($0 \le x_i, y_i \le 10^4$), the coordinates of city $i$. There is a road from city $i$ to city $i+1$ for $1 \le i \le n-1$, and a road from city $n$ to city $1$. Roads can be traveled in either direction.

The next $k$ lines each contain three integers $u$, $v$, and $c$ ($1 \le u, v \le n$, $u \ne v$, $1 \le c \le 10^8$). A road between $u$ and $v$ can be built at cost $c$. No two cities are at the same location. No two candidate roads connect the same pair of cities, and no candidate connects two cities that already have a road.

At least one road must be built. Building all candidate roads makes all routes at most $m$. Changing $m$ by $0.001$ does not change the answer.

Print the minimum cost of a set of roads that keeps all citizens happy.