Egy országban $N$ darab város van, amiket kétirányú utak kötnek össze. Az úthálózatra teljesül, hogy bármelyik városból bármelyikbe el lehet jutni. Két város között legfeljebb egy közvetlen út van. Minden útra adott egy súlykorlátozás, hogy rakománnyal együtt legfeljebb mekkora tömegű teherautó mehet rajta. Egy áruszállító cég nyersanyagokat szállít városok között. A cégnek nem számít, hogy két város között a szállítás milyen hosszú úton történik, de a lehető legtöbb nyersanyagot szeretnék elvinni egy-egy teherautóval. Adott $Q$ darab várospár, amik között nyersanyagot kell szállítani. Minden várospárra adjuk meg, hogy legfeljebb milyen nehéz lehet a teherautó szállítmánnyal.
Bemenet: az első sor tartalmazza a városok $N$ számát, az utak $M$ számát és a várospárok $Q$ számát. A városokat 0-tól $\left(N-1\right)$-ig indexeljük. A következő $M$ sor mindegyike három számot tartalmaz: egy adott út mely városokat köt össze, és mekkora rá a súlykorlátozás. A következő $Q$ sor mindegyike két számot tartalmaz: egy adott várospár indexeit, amik között szállítani kell.
Kimenet: $Q$ sor mindegyikébe egy számot írjunk: azt a maximális súlyt, amilyen nehéz teherautó indulhat az adott várospár között.