== include(page="template/taskheader" task_id="spiridusi") ==
Mei şi Satsuki s-au întors de curând în casa de vacanţă a familiei lor. Această casă este formată din N camere, unite între ele prin N-1 culoare, astfel încât să se poată ajunge din orice cameră în orice altă cameră. Intrarea în casă se face prin camera 1. Deoarece casa n-a fost locuită timp de mai multe luni, în fiecare cameră i s-au stabilit s i spiriduşi de praf.

Cele două fete doresc să-şi amenajeze un spaţiu de joacă întins pe mai multe camere. Ele vor să
stabilească două camere a şi b (nu neapărat distincte), astfel încât drumul cel mai scurt de la
intrarea în casă până în camera b trece prin camera a. Fetele vor merge apoi din camera a în
camera b pe drumul cel mai scurt (fără a trece de două ori prin aceeaşi cameră), gonind spiriduşii de
praf aflaţi în fiecare cameră prin care trec, inclusiv pe cei din camerele a şi b. După ce fetele ajung
în camera b, ele consideră că toate camerele din care au gonit spiriduşii de praf au fost alese pentru
spaţiul de joacă.
Fetele au stabilit pentru fiecare cameră i un coeficient p i care reprezintă cât de plăcută ar fi camera
i pentru spaţiul lor de joacă. În plus, ele au convenit că nu vor goni în total mai mult de C spiriduşi
ai prafului din camerele prin care trec.

h2. Cerinta
h2. Date de intrare