Fişierul intrare/ieşire:	sabotaj.in, sabotaj.out	Sursă	FMI No Stress 2010
Autor	Vlad Duta	Adăugată de	Dumitran Adrian Marius •marius135
Timp execuţie pe test	0.225 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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. 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.

Date de intrare

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.

Date de ieşire

Î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.

Restricţii

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

Exemplu

Cum se trimit solutii?