Baltazar

Ο Baltazar αποφάσισε να πάει διακοπές. Αυτή τη στιγμή είναι στο Baltazagrad και θέλει να ταξιδέψει στο Primosten. Για να φτάσει εκεί, πρέπει να περάσει από πολλές πόλεις. Υπάρχουν ~n~ πόλεις και συνδέονται με ~m~ δρόμους διπλής κυκλοφορίας. Το Baltazagrad επισημαίνεται ως η πόλη με τον αριθμό ~1~ και το Primosten ως η πόλη με τον αριθμό ~n~.

Ο Baltazar δεν είναι σίγουρος σχετικά με την διαδρομή από το Baltazagrad προς το Primosten, οπότε θα χρησιμοποιήσει το GPS. Θα τον οδηγήσει στον προορισμό του χρησιμοποιώντας την πιο σύντομη διαδρομή.

Αλλά στον Baltazar αρέσει να ταξιδεύει και μπορεί να χύσει το μαγικό του φίλτρο σε οποινδήποτε δρόμο (ακόμα και σε κάποιον δρόμο τον οποίο δεν θα περάσει) και να αυξήσει το μήκος του κατά 2 χιλιόμετρα. Μπορεί να το χύσει μόνο σε ένα δρόμο.

Σύντομα συνειδητοποίησε ότι πρέπει να κάνει check-in στο ξενοδοχείο Zora στο Primosten πριν το σούρουπο, οπότε δεν μπορεί να αυξήσει υπερβολικά το μήκος της πιο σύντομης διαδρομής. Τώρα θέλει να μάθει σε πόσους δρόμους μπορεί να χύσει το μαγικό του φίλτρο, έτσι ώστε η μικρότερη απόσταση μεταξύ του Baltazagrad και του Primosten να αυξηθεί κατά 1 χιλιόμετρο ακριβώς.

Βοηθήστε τον να καθορίσει τους δρόμους στους οποίους μπορεί να χύσει το μαγικό του φίλτρο.

Είσοδος

Κάθε έλεγχος περιέχει πολλαπλά αρχεία ελέγχου. Η πρώτη γραμμή περιέχει τον αριθμό των αρχείων ελέγχου ~t~ (~1~ ~\le~ ~t~ ~\le~ ~10\,000~). Ακολουιεί η περιγραφή των αρχείων ελέγχου.

Η πρώτη γραμμή κάθε αρχείου ελέγχου περιέχει τους ακέραιους ~n~ και ~m~ (~2~ ~\le~ ~n~ ~\le~ ~300\,000~, ~1~ ~\le~ ~m~ ~\le~ ~min~(~300\,000~, ~\frac{1}{2}~)), τον αριθμό των πόλεων και τον αριθμό των δρόμων μεταξύ των πόλεων.

Οι επόμενες ~m~ γραμμές περιέχουν ακέραιους ~a_i~, ~b_i~, ~w_i~ (~1~ ~\le~ ~a_i~, ~b_i~ ~\le~ ~n~, ~a_i~ ~\ne~ ~b_i~, ~1~ ~\le~ ~w_i~ ~\le~ ~10^9~), που σημαίνουν ότι υπάρχει ένας δρόμος μεταξύ της πόλης ~a_i~ και ~b_i~, και το μήκος του είναι ~w_i~. Μεταξύ κάθε ζεύγους πόλεων, υπάρχει το πολύ ένας δρόμος που τις ενώνει.

Όλες οι πόλεις συνδέονται, π.χ, για κάθε ζεύγος πόλεων, υπάρχει ένα μονοπάτι από τη μια στην άλλη, αλλά δεν είναι απαραίτητα άμεσο.

Είναι εγγυημένο ότι το άθροισμα των ~n~ από όλα τα αρχεία ελέγχου δεν ξεπερνά τις ~300\,000~ και ότι το άθροισμα των ~m~ από όλα τα αρχεία ελέγχουν δεν ξεπερνά τις ~300\,000~.

Έξοδος

Στην πρώτη γραμμή, εκτυπώστε τον ακέραιο ~c~, τον αριθμό των δρόμων στους οποίου ξύνει ο Baltazar το μαγικό του φίλτρο. Στη δεύτερη γραμμή, εκτυπώστε ~c~ ακέραιους, τους δείκτες των δρόμων σε αύξουσα σειρά.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	15	~n~, ~m~ ~\le~ ~1\,000~
2	30	Υπάρχει ένας δρόμος μεταξύ του Baltazagrad και του Primosten και το μήκος του είναι ~1~ χιλιόμετρο μεγαλύτερο από την μικρότερη απόσταση μεταξύ αυτών των πόλεων
3	65	Κανένας επιπλέον περιορισμός.

Παραδείγματα

input

3
6 6
1 2 2
1 3 2
2 4 2
3 5 2
4 5 1
5 6 2
6 6
1 2 2
1 3 2
2 4 2
3 5 2
4 5 3
5 6 2
6 7
1 2 2
1 3 2
2 4 2
3 5 2
4 5 1
5 6 2
1 6 7

output

2
2 4
0

3
2 4 6

Επεξήγηση του παραδείγματος

Οι πόλεις και οι δρόμοι φαίνονται στην παρακάτω εικόνα. Αν ο Baltazar χύσει το μαγικό του φίλτρο στο δρόμο ~2~ (μεταξύ των πόλεων ~1~ και ~3~), ή στο δρόμο ~4~ (μεταξύ των πόλεων ~3~ και ~5~), τότε η μικρότερη απόσταση μεταξύ των πόλεων ~1~ και ~n~ θα αυξηθεί κατά ~1~.