B - Fabryki

Autor: Michał Rein, Łukasz Olek

Firma Bajtlad ma sieć fabryk. Wszystkie fabryki są położone z dala od miast. Koszty zatrudnienia w jednym mieście są stałe, ale między miastami zdarzają się znaczne różnice. Fabryki zatrudniali pracowników z miast najbliżej nich położonych, opłacając ich przejazd z domu do pracy. W ostatnim czasie została wybudowana sieć bardzo szybkich kolei. Czas przejazdu między dwoma najbardziej odległymi miejscami jest tak krótki, że możliwe wydaje się zatrudnianie pracowników mieszkających nawet w najbardziej odległych od danej fabryki miastach.

Zostałeś poproszony o obliczenie minimalnego kosztu zatrudnienia pracowników we wszystkich fabrykach, zakładając, że fabryki nadal będą opłacały koszty dojazdu pracowników. Taka kalkulacja może pomóc w znacznym obniżeniu kosztów działalności firmy.

Zadanie

Dla każdego zestawu danych oblicz minimalny sumaryczny dzienny koszt zatrudnienia we wszystkich fabrykach, uwzględniając koszty podróży.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita dodatnia, określająca liczbę zestawów danych. Każdy zestaw danych zawiera kolejno informacje o fabrykach, miastach i sieci kolei. Informacje o fabrykach zaczynaja się jedną liczbą naturalną N1 , określająca liczbę fabryk. Każda fabryka opisana jest w jednym wierszu przez dwie liczby naturalne. Pierwsza to ID będąca indentyfikatorem fabryki. Druga, niezerowa, mówi ile fabryka zatrudnia pracowników. Następnie zaczynają się informacje o miastach, jedną liczbą naturalną N2, określającą liczbę miast. Każde miasto opisane jest w jednym wierszu przez dwie liczby naturalne. Pierwsza to ID będąca indentyfikatorem miasta. Druga, niezerowa, mówi jaki jest koszt zatrudnienia jednego pracownika w danym mieście. Następnie na wejściu znajduje się opis sieci kolei. Opis zaczyna się jedną liczbą naturalną M, określającą liczbę linii kolejowych. Każda linia opisana jest przez trzy liczby naturalne. Dwie pierwsze to ID, mówiące jakie dwa obiekty (obiekt to fabryka lub miasto) łączy dana linia. Trzecia, niezerowa, określa koszt przejazdu jednej osoby daną linią.

Dane wejściowe spełniają następujące warunki:
Każdy obiekt ma unikalne ID
1 <= ID <= 100000
1 <= N1+N2 <= 100
1 <= M <= 10000
Łączne zapotrzebowanie wszystkich fabryk (liczba osób) < 100000
Maksymalny sumaryczny koszt transportu jednej osoby miedzy dwoma najbardziej oddalonymi obiektami < 20000
Maksymalny koszt zatrudnienia jedenj osoby < 100000
Każda linia łączy dwa różne obiekty. Dwa różne obiekty mogą być polączone tylko jedną bezposrednią linią.
Na każdej linii można jeździć w obie strony. Koszt przejazdu w obie strony jest taki sam. Fabryka nie musi byc połączona bezpośrednio z miastem. Każda fabryka jest poąłczona bezpośrednio lub pośrednio z co najmniej jednym miastem.
Dla uproszczenia przyjmujemy, że wszystkie miasta mają wystarcząjaco dużo mieszkanców chętnych do pracy.

Wyjście

Dla każdego zestawu danych wypisać jeden wiersz zawierąjcy jedną liczbę naturalną, okrelającą minimalny, sumaryczny, dzienny koszt zatrudnienia pracowników w fabrykach.

Przykładowe wejście

2
1
32 8
1
45 2
1
45 32 10
2
1 2
2 1
2
3 3
4 1
3
1 2 3
2 3 2
3 4 1

Przykładowe wyjcie

96
18