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

Firma A1-809 detine o retea formata din $N$ calculatoare numerotate de la $1$ la $N$ conectate intre ele prin $M$ cabluri astfel incat oricare doua calculatoare pot comunica intre ele fie direct printr-un cablu, fie prin intermediul altor calculatoare de care sunt conectate. Dumneavoastra lucrati pentru firma C-109 care se afla in concurenta cu A1-809 si aveti misiunea de a sabota reteaua acestora. Ceea ce aveti de facut este sa incercati sa taiati cateva dintre cele $M$ cabluri care conecteaza calculatoarele, astfel incat intre cel putin doua calculatoare sa nu mai existe conexiune. Pentru a nu fi prins de paznicul nea' Fane trebuie ca timpul necesar operatiunii sa fie minim.

Firma A1-809 detine o retea formata din $N$ calculatoare numerotate de la $1$ la $N$ conectate intre ele prin $M$ cabluri astfel incat oricare doua calculatoare pot comunica intre ele fie direct printr-un cablu, fie prin intermediul altor calculatoare de care sunt conectate. Intre oricare doua calculatoare exista cel mult un cablu. Dumneavoastra lucrati pentru firma C-109 care se afla in concurenta cu A1-809 si aveti misiunea de a sabota reteaua acestora. Ceea ce aveti de facut este sa incercati sa taiati cateva dintre cele $M$ cabluri care conecteaza calculatoarele, astfel incat intre cel putin doua calculatoare sa nu mai existe conexiune. Pentru a nu fi prins de paznicul nea' Fane trebuie ca timpul necesar operatiunii sa fie minim.

Cunoscand pentru fiecare cablu care este timpul necesar taierii lui, determinati care cabluri trebuie taiate pentru a rupe orice legatura intre cel putin doua calculatoare din reteaua A1-809 in cel mai scurt timp posibil.
h2. Date de intrare

Fişierul de intrare $sabotaj.in$ ...

Fişierul de intrare $sabotaj.in$ contine pe prima linie doua numere naturale $N$ si $M$ reprezentand numarul de calculatoare, respectiv numarul de cabluri din retea. Urmatoarele $M$ linii contin cate trei numere naturale: $x$, $y$ si $t$ cu semnificatia ca exista un cablu care conecteaza calculatorul $x$ de calculatorul $y$ si a carui taiere necesita $t$ secunde.

h2. Date de ieşire

În fişierul de ieşire $sabotaj.out$ ...

În fişierul de ieşire $sabotaj.out$ se vor afisa pe prima linie doua numere: $tmin$ si $k$ reprezentand numarul minim de secunde necesare operatiunii precum si numarul de cabluri care trebuie taiate, in acesta ordine si separate printr-un spatiu. Urmatoarele $k$ linii vor contine fiecare cate un numar, astfel pe cea de-a $i+1$-a linie din fisierul de iesire se va afla indicele celei de-a $i$-a muchie taiata. Muchiile se considera numerotate de la $1$ la $M$ in ordinea din fisierul de intrare si vor fi afisate in ordine crescatoare a indicelui.
Daca exista mai multe solutii toate avand acelasi timp total minim veti afisa oricare dintre ele.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $2 ≤ N ≤ 200$
* $1 ≤ M ≤ 3500$
* $1 ≤ timpul necesar taierii unui cablu ≤ 1024$

h2. Exemplu
table(example). |_. sabotaj.in |_. sabotaj.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 5 7
  3 4 2
  1 5 2
  5 2 8
  1 3 7
  2 3 1
  4 1 9
  5 4 5
| 8 3
  2
  5
  7

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="sabotaj") ==

5129