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

X vrea să facă o excursie într-un oraş în formă de arbore cu $N$ noduri. Pentru fiecare muchie de la $u$ la $v$ se cunosc coeficientul de frumuseţe $a$ al parcurgerii muchiei de la $u$ la $v$ şi coeficientul de frumuseţe $b$ al parcurgerii muchiei de la $b$ la $a$ ( $a$ şi $b$ numere întregi). X poate merge oricum pe muchiile arborelui, însă la final îşi va aduce aminte numai ultima dată când a vizitat o muchie. Coeficientul total este suma coeficienţilor muchiilor pe care X îşi aminteşte că le-a vizitat. Pentru a se hotărî din ce nod să înceapă excursia, X te roagă să afli coeficientul total maxim care se poate obţine plecând din fiecare nod din cele $N$.

X vrea să facă o excursie într-un oraş în formă de arbore cu $N$ noduri. Pentru fiecare muchie de la $u$ la $v$ se cunosc coeficientul de frumuseţe $a$ al parcurgerii muchiei de la $u$ la $v$ şi coeficientul de frumuseţe $b$ al parcurgerii muchiei de la $v$ la $u$ ( $a$ şi $b$ numere întregi). X poate merge oricum pe muchiile arborelui, însă la final îşi va aduce aminte numai ultima dată când a vizitat o muchie. Coeficientul total este suma coeficienţilor muchiilor pe care X îşi aminteşte că le-a vizitat. Pentru a se hotărî din ce nod să înceapă excursia, X te roagă să afli coeficientul total maxim care se poate obţine plecând din fiecare nod din cele $N$.

h2. Date de intrare