h2. Cerinţa

Dându-se un graf neorientat $G(V,E)$, si trei noduri $A,B,C ⊆ V$ determinaţi numărul de trilanţuri de cost minim cu varfurile in $A,B,C$.

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.

h2. Date de intrare

h2. Date de ieşire

Fişierul $trilant.out$ va conţine o singură linie pe care se vor găsi numărul de trilanţuri de cost minim si costul minim găsit.

Fişierul $trilant.out$ va conţine pe prima linie costul minim găsit. Fiecare din următoarele trei linii va avea urmatorul format: $K$, urmat de $K$ numere $x{~1~},x{~2~}...x{~k~}$, reprezentand unul din cele trei lanţuri ce formeză un trilanţ. Cele trei lanţuri pot fi afişate oricum. În caz că există mai multe trilanţuri de cost minim se va afişa oricare dintre ele.

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

* $-50 000 ≤ C ≤ 50 000$
* Nu vor exista cicluri de cost negativ de lungime $≥ 3$

* $0 ≤ C ≤ 50 000$

* 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)$

1 4 1
2 4 1
3 4 1

| 1 3

| 3
2 1 4
2 2 4
2 3 4

|
== include(page="template/taskfooter" task_id="trilant") ==