Problem C
Torrent Routing

John försöker ladda ner en fil med hjälp av en torrent. Torrents fungerar genom att lagra data vid många användare som andra användare kan ladda ner och ladda upp data till och från. För att ladda ner filen som John vill ha måste han ansluta till flera användare och ladda ner den datan som behövs för att avsluta sin fil. Problemet är att John - som är lite sus - behöver vara helt anonym. För att lösa detta problem har John beslutat sig för att route:a sin internettrafik genom ett antal servrar för att gömma sin IP-address. Internet bredbandet mellan servrar och användare kan variera. Servrar ansluter endast till vissa servrar och användare. Givet hur nätverket av servrar och användare ser ut.
Det är givet att Johns pc alltid har id:et $0$ och att varje användare har ett unikt id, det är även garanterat att John kan ansluta sig till varje nödvändig användare genom någon serie av anslutningar.
John kan endast ladda ner en byte av data per tidsenhet och tiden det tar för att ladda ner datan du behöver från en viss användare är sum av nedladdningstiden av alla servrar i den serie av anslutningar som kopplar till denne. Tiden det tar för en given filnedladdning mellan två servrar är $\frac{F_ i}{W_ i}$
Givet allt detta, hjälp John att hitta den minimala filnedladdningstiden för sin fil ifall han route:ar sin internettrafik optimalt.

Indata

Den första raden av indata består av två icke-negativa heltal $B$ $(1 \leqslant B \leqslant 3000)$, antalet olika användare som John behöver ansluta sig till, och $N$ $(1 \leqslant N \leqslant 3000)$, antalet olika servrar/användare
De följande $B$ linjerna innehåller två stycken icke-negativa heltal: $U_ i$, $F_ i$, $(1 \leqslant U_ i \leqslant N, 1 \leqslant F_ i \leqslant 10^9)$ id:et för användaren och storleken på filen som John behöver från den personen (i bits).
Nästa rad innehåller ett heltal $M$ $(1 \leqslant M \leqslant 30000)$, antalet anslutningar mellan servrar och användare (inklusive John).
Sedan följer $M$ linjer som innehåller tre stycken heltal $X_ i$, $Y_ i$, $W_ i$ ($1 \leqslant X_ i, Y_ i \leqslant 3000, 1 \leqslant W_ i \leqslant 10^9$) som visar att det finns en anslutning mellan de servrar/användare med id $X_ i$ och $Y_ i$, vars nedladdningshastighet är $W_ i$ bits/sekund.

1 Utdata

Skriv ut ett heltal, det minimala antalet sekunder (rundat uppåt till närmsta heltal större) det tar för John att ladda ner all den nödvändiga datan för att avsluta sin fil.

2 Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp måste du klara alla testfall i gruppen.

Förklaring till Sample 1

Den snabbaste metoden är att route:a genom server 2. Vägen 0-1-2-3 tar $\frac{100}{10} + \frac{100}{10} + \frac{100}{21} = 24.762$ sekunder. Alltså är svaret $25$ sekunder.

1 3
3 100
4
0 1 10
1 3 1
1 2 10
2 3 23

25