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

== include(page="template/detailed-feedback" task_id="trilant") ==
 
Într-un graf neorientat $G=(V,E)$ cu costuri pe muchii, definim un lanţ ca fiind o succesiune de noduri $S={x{~1~},x{~2~}...x{~k~}}$, cu condiţia să existe muchie între oricare două noduri consecutive, si toate nodurile să fie diferite. Costul unui lanţ este reprezentat de suma costurilor muchiilor alese pentru a uni x{~1~} cu x{~2~}, x{~2~} cu x{~3~} ... x{~k-1~} cu x{~k~}. Vom nota un lanţ $(x{~1~},x{~2~}...x{~k~})$ prin primul si ultimul său nod, adică : $(x{~1~},x{~k~})$. Definim un trilanţ ca fiind reuniunea a trei lanţuri $(A,X),(B,X),(C,X); A,B,C,X ⊆ V$, $X$ fiind singurul nod comun celor trei. Costul unui trilanţ este egal cu suma costurilor celor trei lanţuri care îl formează. Vom nota un trilanţ prin $(A,B,C)$.

Într-un graf neorientat $G=(V,E)$ cu costuri pe muchii, definim un lanţ ca fiind o succesiune de noduri $S={x{~1~},x{~2~}...x{~k~}}$, cu condiţia să existe muchie între oricare două noduri consecutive, si toate nodurile să fie diferite. Costul unui lanţ este reprezentat de suma costurilor muchiilor alese pentru a uni $x{~1~}$ cu $x{~2~}, x{~2~} cu x{~3~} ... x{~k-1~}$ cu $x{~k~}$. Vom nota un lanţ $(x{~1~},x{~2~}...x{~k~})$ prin primul si ultimul său nod, adică : $(x{~1~},x{~k~})$. Definim un trilanţ ca fiind reuniunea a trei lanţuri $(A,X),(B,X),(C,X); A,B,C,X ⊆ V$, $X$ fiind singurul nod comun celor trei. Costul unui trilanţ este egal cu suma costurilor celor trei lanţuri care îl formează. Vom nota un trilanţ prin $(A,B,C)$.

h2. Cerinţa

h2. Restricţii
* $1 ≤ A, B, C ≤ N ≤ 100 000$

* $1 ≤ M ≤ 500 000$
* $1 ≤ costul unei muchii ≤ 20 000$

* $1 ≤ M ≤ 250 000$
* $1 ≤ costul unei muchii ≤ 4 000 000$

* Pentru $50%$ din teste $N ≤ 1 000$
* Lanţurile care formează un trilanţ pot avea lungimi diferite
* Oricare trei lanţuri $(A,X),(B,X),(C,X)$ care formează un trilanţ vor fi disjuncte două cate două, mai puţin nodul $X$ (singurul nod comun pe care îl vor avea va fi $X$)

4268