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

Într-un graf neorientat $G(V,E)$, un lanţ reprezintă un set de noduri $S={x{~1~},x{~2~}...x{~k~}}$, astfel încât există muchie între oricare două noduri consecutive din lanţ. Costul unui lanţ este 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 $(x1,xk)$.
Definim un trilanţ într-un graf neorientat $G(V,E)$ 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 suma costurilor celor trei lanturi care il formează.

Într-un graf neorientat $G = (V,E)$, un lanţ reprezintă o succesiune de noduri $S={x{~1~}, x{~2~}, ..., x{~k~}}$, astfel încât există muchie între oricare două noduri consecutive. Costul unui lanţ este 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ă astfel: $(x1, xk)$.
Definim un trilanţ într-un graf neorientat $G = (V,E)$ 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 suma costurilor celor trei lanţuri care îl formează.

h2. Cerinţa

Dându-se un graf neorientat $G(V,E)$, si trei noduri $A,B,C ⊆ V$ determinaţi costul minim al unui trilant cu varfurile in $A,B,C$, precum si acest trilant.

Dându-se un graf neorientat $G = (V,E)$ şi trei noduri $A, B, C ⊆ V$, determinaţi costul minim al unui trilanţ cu vârfurile in $A, B, C$, precum şi acest trilanţ.

h2. Date de intrare

Pe prima linie a fişierului $trilant.in$ se află două numere naturale $N, M$ separate printr-un spaţiu, reprezentând numărul de noduri, respectiv numărul de muchii din graf. Pe a doua linie a fişierului de intrare se vor afla numerele naturale $A,B,C$ cu semnificaţia din enunţ.
Următoarele $M$ linii vor conţine câte trei numere $P,Q,X$ descriind faptul ca există muchie de la nodul $P$ la nodul $Q$ cu costul $X$.

Pe prima linie a fişierului $trilant.in$ se află două numere naturale $N, M$ separate printr-un spaţiu, reprezentând numărul de noduri, respectiv numărul de muchii din graf. Pe a doua linie a fişierului de intrare se vor afla numerele naturale $A, B, C$ cu semnificaţia din enunţ.
Următoarele $M$ linii vor conţine câte trei numere $P, Q, X$ descriind faptul ca există muchie de la nodul $P$ la nodul $Q$ cu costul $X$.

h2. Date de ieşire

h2. Restricţii

* $1 ≤ A,B ≤ N ≤ 100 000$

* $1 ≤ A, B ≤ N ≤ 100 000$

* $1 ≤ M ≤ 100 000$
* $1 ≤ C ≤ 50 000$
* Pentru $30%$ din teste $N ≤ 1 000$
* Gradul maxim al unui nod din graf este $10$

* 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$)
* Oricare trei lanţuri $(A,X),(B,X),(C,X)$ care formează un trilanţ vor avea lungime $≥ 2 (A ≠ X, B ≠ X, C ≠ X)$

* 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$)
* Oricare trei lanţuri $(A,X), (B,X), (C,X)$ care formează un trilanţ vor avea lungime $≥ 2 (A ≠ X, B ≠ X, C ≠ X)$

h2. Exemplu