h2. Cerinta

Pentru un numar considerabil de actiuni la Alfatrans si pentru a ob�£ine $100$ de puncte, trebuie sa-l ajutati pe patronul firmei Alfatrans sa stabileasca pentru fiecare oras profitul impus de primarie astfel incat firma Betatrans sa fie discreditata.

Pentru un numar considerabil de actiuni la Alfatrans si pentru a obtine $100$ de puncte, trebuie sa-l ajutati pe patronul firmei Alfatrans sa stabileasca pentru fiecare oras profitul impus de primarie astfel incat firma Betatrans sa fie discreditata.

h2. Date de intrare

Pe prima linie a fisierului de intrare $import.in$ sunt scrise numerele naturale $N M K$ separate prin cate un spatiu, avand semnificatia din enunt. Urmatoarele $N-1$ linii contin cate doua numere naturale $a b$ separate printr-un spatiu, cu semnificatia ca exista o sosea bidirectionala de la orasul $a$ la orasul $b$. Urmatoarele $M$ linii descriu transporturile dupa cum urmeaza. Fiecare linie contine 4 numere $a b c d$ separate prin cate un spatiu cu semnificatia "se face transport de la orasul $a$ la orasul $b$ executat de firma $x$, iar profitul minim ce trebuie asigurat pentru acest transport este $c$". Firma $x$ este Alfatrans dac�� $d=0$ si respectiv Betatrans daca $d=1$. Se garanteaza ca pentru orice transport $a$ este un oras din afara tarii, iar $b$ este un oras din Romania.

Pe prima linie a fisierului de intrare $import.in$ sunt scrise numerele naturale $N M K$ separate prin cate un spatiu, avand semnificatia din enunt. Urmatoarele $N-1$ linii contin cate doua numere naturale $a b$ separate printr-un spatiu, cu semnificatia ca exista o sosea bidirectionala de la orasul $a$ la orasul $b$. Urmatoarele $M$ linii descriu transporturile dupa cum urmeaza. Fiecare linie contine 4 numere $a b c d$ separate prin cate un spatiu cu semnificatia "se face transport de la orasul $a$ la orasul $b$ executat de firma $x$, iar profitul minim ce trebuie asigurat pentru acest transport este $c$". Firma $x$ este Alfatrans dac��� $d=0$ si respectiv Betatrans daca $d=1$. Se garanteaza ca pentru orice transport $a$ este un oras din afara tarii, iar $b$ este un oras din Romania.

h2. Date de iesire