최소 비용 배달

Abu는 한 도시에서 다른 도시로 물건을 배송하는 배달 서비스를 운영한다. 어느 날 Abu는 배달해야 할 물건 $k$개를 받았다. 각 물건은 출발 도시에서 도착 도시로 배달해야 하며, 한 번에 하나의 물건만 배달할 수 있다. 대신 모든 물건을 배달하기만 하면 배달 순서는 자유롭게 정할 수 있다. Abu는 어떤 물건의 출발 도시에서 시작해 그 물건을 도착 도시까지 배달하고, 다음 물건의 출발 도시로 이동해 배달을 이어 가며, 물건이 남지 않을 때까지 이를 반복한다.

모든 도로는 양방향이며, 두 도시 사이에는 여러 도로가 있을 수 있다. Abu는 어떤 도로든 원하는 만큼 반복해서 이용할 수 있다.

도시 목록, 도시 사이의 도로와 길이, 배달 목록이 주어졌을 때, 가장 효율적인 순서로 모든 배달을 마치는 데 필요한 최소 총 이동 거리를 구하라.

첫째 줄에 도시의 수, 도로의 수, 물건의 수를 나타내는 세 정수 $n, m, k$가 주어진다 ($2 \le n, m \le 10^4$, $1 \le k \le 18$).

다음 $m$개 줄에는 세 정수 $u_i, v_i, l_i$가 주어진다 ($1 \le u_i, v_i \le 10^4$, $1 \le l_i \le 10^6$). 이는 도시 $u_i$와 도시 $v_i$를 잇는 길이가 $l_i$인 도로가 있음을 의미한다.

다음 $k$개 줄에는 두 정수 $f_i, d_i$가 주어진다 ($1 \le f_i, d_i \le 10^4$). 이는 $i$번째 물건을 도시 $f_i$에서 도시 $d_i$로 배달해야 함을 의미한다.

모든 물건을 최적 순서로 배달했을 때의 최소 총 이동 거리를 하나의 정수로 출력한다. 모든 물건을 배달하는 것이 불가능하면 $-1$을 출력한다.

첫 번째 경우, 도시 $5$에서 시작해 세 번째 물건을 도시 $3$까지 배달하고, 도시 $1$로 이동한 뒤 두 번째 물건과 첫 번째 물건을 순서대로 배달하면 총 이동 거리가 $12$가 되며, 이것이 최소이다.

두 번째 경우, 도시 $1$, $2$, $4$와 도시 $3$, $5$ 사이를 잇는 경로가 없어 모든 물건을 배달할 수 없다.