== include(page="template/taskheader" task_id="gather") ==

Bunul nostru prieten Gigel a ajuns la inchisoare. Inchisoarea are $N$ celule legate intre ele prin $M$ coridoare ce pot fi parcurse in ambele sensuri. In inchisoare se afla in total $K$ detinuti. Foarte inteligent si practic Gigel are deja un plan de evadare, dar pentru asta are nevoie de toti detinutii. Initial Gigel se afla in celula {$1$}, iar modul in care ii poate aduna pe detinuti este urmatorul: el se plimba prin coridoarele inchisorii si cand intalneste un nou detinut ii spune planul si in continuare acesta va trebui sa il urmeze(Gigel vrea sa se asigure ca nici un detinut nu il va trada, de aceea nu scapa din ochi nici un detinut care stie de planul sau). Problema este ca daca pe anumite coridoare sunt vazuti mai multi detinuti mergand impreuna, paznicii inchisorii vor intra la banuieli, iar planul lui Gigel va esua. Deoarece vrea ca toti sa fie cat mai odihniti Gigel doreste sa minimizeze suma totala parcursa de toti detinutii si de el. Detinutii stau pe loc pana in momentul in care Gigel vine la ei, apoi il vor urma intotdeauna.
 
h2. Cerinta
 
Calculati suma minima a distanelor parcurse de detinuti si de Gigel pentru a-i aduna pe toti intr-o celula.

Poveste si cerinta...

h2. Date de intrare

Fisierul de intrare $gather.in$ contine pe prima linie trei numere naturale {$K$}, {$N$}, {$M$}. Pe urmatoarele {$K$} linii se afla cate un numar reprezentand celulele in care se afla initial detinutii. In continuare vor urma {$M$} linii fiecare continand cate patru numere naturale $A$ $B$ $C$ $D$ cu urmatoare semnificatie: intre celulele $A$ si $B$ se afla un coridor de lungime $C$ pe care nu pot merge mai mult de $D$ detinuti.

Fisierul de intrare $gather.in$ ...

h2. Date de iesire

In fisierul de iesire $gather.out$ se va afla o singura linie care contine distanta minima ceruta.

In fisierul de iesire $gather.out$ ...

h2. Restrictii

* $1 ≤ N ≤ 750$
* $1 ≤ K ≤ 15$
* $1 ≤ M ≤ 1250$

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. gather.in |_. gather.out |

| 2 4 5
4
2
1 2 50 1
2 3 75 2
2 4 25 1
3 4 100 2
3 1 10 2
| 400

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicatie

Gigel merge din celula $1$ in celula $2$ parcurgand o distanta de {$50$}. Aici ii spune detinutului $2$ de planul sau.
Gigel merge apoi impreuna cu detinutul $2$ in celula $3$ parcurgand impreuna distanta {$2*75$}.
Gigel merge apoi impreuna cu detinutul $2$ in celula $4$ parcurgand impreuna distanta {$2*100$}. Aici este informat si detinutul $2$ de plan.
 

...

== include(page="template/taskfooter" task_id="gather") ==