---
# System prepended metadata

title: Okoli sveta

---

# Okoli sveta

Nina je nabrala večjo vsoto denarja, da lahko izpolni svoj življenjski cilj - pot okoli sveta. Stroške bo plačevala s kartico, a ji je banka namenila strogo omejitev, koliko denarja lahko porabi v enem nakupu. Zato mora Nina dobro pripraviti načrt poti. 

Na poti želi obiskati nekaj izmed $N$ mest, ki so označena s števili med $1$ in $N$. Ugotovila je tudi, da ji je na voljo $M$ letalskih povezav, ki povezujejo mesta. Da bi bila pot čimbolj zanimiva, se je odločila, da si vsak dan ogleda eno mesto. Nino zanima najmanjša vsota maksimalnih cen letalskih vozovnic, s katerimi bo potovala okoli sveta. Zastavila ti bo nekaj vprašanj, ki sestojijo iz začetnega in končnega mesta, na dano vprašanje pa jo zanima najvišja cena vozovnice, ki jo mora Nina plačati, da pripotuje med izbranima krajema. Napiši program, ki odgovori na $Q$ takšnih vprašanj.

## Vhod

V prvi vrstici standardnega vhoda se nahajata celi števili $N$ in $M$.

V naslednjih $M$ vrsticah so podana tri cela števila $u$, $v$ in $w$ $(u \neq v)$, ki opisujejo letalsko povezavo med krajema $u$ in $v$, cena vozovnice je enaka $w$. 

V naslednji vrstici je podan $Q$. 

Tej vrstici sledi $Q$ vrstic s celima številoma $s$ in $f$ $(s \neq f)$, ki opisujeta tekoče vprašanje za pot, ki se prične v mestu $s$ in konča v mestu $f$.

## Izhod

Na izhod izpiši vsoto odgovorov na vprašanja.

## Omejitve

- $2 \leq N, M \leq 10^5$
- $1 \leq Q \leq 10^6$
- $1 \leq u, v, s, f \leq N$
- $1 \leq w \leq 10^9$

## Primer

Vhod:
```
7 10
1 2 4
1 4 8
2 3 2
2 5 9
3 4 1
3 7 3
4 6 6
4 7 7
5 7 5
6 7 10
3
1 5
2 4
3 6
```

Izhod:
```
13
```

## Komentar

![](https://i.imgur.com/UTw3JYh.png)

V tem primeru imamo $7$ mest povezanih z $10$ letalskimi povezavami. Število vprašanj je $3$. 

Prvo vprašanje je $s = 1$ in $f = 5$. Da bi prispeli na cilj (mesto $5$) moramo uporabiti eno od linij $7 \to 5$ ali $2 \to 5$. Izberemo $7 \to 5$, ker je cenejša. Zatorej je odgovor na to vprašanje $5$.

Pri naslednjih vprašanjih opazimo, da sta optimalni smeri $2 \to 3 \to 4$ in $3 \to 4 \to 6$. Če želimo, da Nina uspešno prepotuje svet, sta minimalni omejitvi banke $2$ in $6$. Končen odgovor je torej $13$, kar je vsota odgovorov na vsa vprašanja: $13 = 5 + 2 + 6$