용구슬 II

옛날 X 행성에는 용구슬에 관한 전설이 있었다. 용구슬을 일곱 개 모으면 용신이 나타나 소원을 들어준다는 이야기다.

그러나 각 구슬의 위치를 알려 주는 용구슬 레이더가 발견된 뒤로 구슬을 모으기가 너무 쉬워졌다. 용신은 시시한 소원에 시달리다 못해 구슬 모으기를 어렵게 만들기로 했다. 이제 구슬은 일곱 개가 아니라 아주 많이 만들어졌고, 각 구슬에는 일련번호가 붙어 있다. 같은 번호의 구슬이 여러 개 있을 수도 있다. 용신을 소환하려면 일련번호가 모두 다른 구슬 일곱 개를 모아야 한다. 같은 번호의 구슬은 중복으로 치지 않는다.

당신은 벼룩시장에서 용구슬 레이더를 샀다. 이 레이더는 각 구슬이 있는 도시와 그 일련번호를 알려 준다. 그래도 용신을 소환하는 가장 싼 방법을 찾을 수 있겠는가?

X 행성에는 1번부터 n번까지 n개의 도시가 있다. 당신은 지금 1번 도시에 있다. 도시 사이를 이동하려면 m개의 양방향 순간이동 노선 중 아무거나 골라 원하는 만큼 쓸 수 있다. i번째 노선은 도시 a_i와 b_i를 잇고, 한 번 쓸 때마다 t_i 코인이 든다. 구슬을 주우려면 그 구슬이 있는 도시를 방문하기만 하면 된다. 같은 도시에 구슬이 여러 개 있을 수 있으며, 그 도시를 방문하면 구슬을 한꺼번에 모두 줍는다.

첫 줄에 세 정수 n, m, k가 주어진다 (1 ≤ n, k ≤ 1 000, 1 ≤ m ≤ 10 000). 각각 도시의 수, 순간이동 노선의 수, 구슬의 수다.

이어서 m개의 줄에 세 정수 a_i, b_i, t_i가 주어진다 (1 ≤ a_i, b_i ≤ n, 0 ≤ t_i ≤ 10 000). 도시 a_i와 b_i를 잇는 노선이며, 한 번 쓸 때마다 t_i 코인이 든다는 뜻이다.

이어서 k개의 줄에 두 정수 c_i, d_i가 주어진다 (1 ≤ c_i, d_i ≤ n). i번째 구슬은 도시 c_i에 있고 일련번호는 d_i이다. 같은 도시에 구슬이 여러 개 있을 수 있고, 같은 일련번호의 구슬이 여러 개 있을 수 있으며, 같은 도시에 같은 일련번호의 구슬이 여러 개 있을 수도 있다.

일련번호가 모두 다른 구슬 일곱 개를 모으는 데 드는 최소 코인 수를 출력한다. 그 작업이 불가능하면 -1을 출력한다.