# Zkouška 9.6 – Holan - Pergel


Je dán neorientovaný ohodnocený graf místa s $N$ vrcholy. Ohodnocení hran udává počet vody, kterou spotřebuje karavana při cestě po této hraně

Máme *karavanu*, která:
- začíná ve vrcholu $V$,
- má maximální kapacitu vaků s vodou $C$
- Počáteční stav vody $Z$

Řekněme, že karavana spotřebuje litr vody na hodinu

Některá místa jsou oázy, kde se doplní vaky s vodou na maximum, těchto oáz je nejvýše $O$ a můžeme je navštívit opakovaně

---
Je dána množina $U$ míst (k navštívení), které je nutné navštívit v libovolném pořadí. Cílem je najít libovolný časový sled pohybu karavany po grafu (hrany se mohou opakovat), který:
- začíná ve vrcholu $V$,
- navštíví všechna města ze seznamu $S$,
- zohledňuje omezení karavany a nutnost doplnění vody.

Není zaručeno, že takový sled existuje.

---
Vstup
1. Hrany grafu ve tvaru:
$[\text{místo1} \ \text{cena} \ \text{místo2}]$
2. Počáteční informace o karavaně ve tvaru:
$[V \ C \ B]$
    - $V$ je název počátečního města
    - $C$ je maximální kapacita vaků s vodou
    - $Z$ je počáteční stav vody
3. Seznam oáz (názvy míst)
4. Seznam míst k navštívení (názvy míst, které je třeba navštívit)

---
Výstup

Pokud existuje požadovaný sled, vypište jej ve formátu:
$[místo \ čas]$

Pro každé místo, které v rámci sledu navštívíme, vypíšeme:
- název města.
- čas příjezdu (např. 00:00, 01:20, atd.),

Čas začíná od 00:00.