Praktični

Ενώ έγραφε εξετάσεις, ο Ivan αντιμετώπισε προβλήματα με την ακόλουθη εργασία:
«Στην είσοδο υπάρχει ακέραιος αριθμός ~N~. Βρείτε το ~N~-οστό ψηφίο του αριθμού 0.135791113151719 ..."

Για να καταφέρει στην επόμενη προσπάθεια να περάσει τις εξετάσεις και έτσι να γλιτώσει από την επανάληψη του ακαδημαϊκού έτους, αποφάσισε να εξασκηθεί με το να είναι ο κύριος χαρακτήρας σε εργασίες όπως οι εξής:

Δίνεται ένας μη κατευθυνόμενος γράφος ~N~ κόμβων και ~M~ ακμών. Κάθε ακμή έχει μια τιμή, έναν ακέραιο αριθμό μικρότερο από ~10^9~.
Ένας απλός κύκλος (κύκλος χωρίς επαναλαμβανόμενους κόμβους) είναι καλός εάν το δυαδικό αποτέλεσμα της λογικής πύλης XOR (bitwise XOR) όλων των τιμών των ακμών του κύκλου είναι ίσο με μηδέν.
Ο Ivan μπορεί να κάνει μια σειρά από πράξεις στο γράφημα. Μια λειτουργία αποτελείται από τα ακόλουθα βήματα:

• Ο Ivan επιλέγει έναν ακέραιο αριθμό ~x~;
• έπειτα, επιλέγει ένα μη κενό υποσύνολο ακμών του δεδομένου γραφήματος;
• και, στη συνέχεια, εφαρμόζει την XOR μεταξύ του αριθμού ~x~ και όλων των επιλεγμένων ακμών (εάν μία από τις επιλεγμένες ακμές έχουν μια τιμή ~p~, μετά την προηγηθείσα διαδικασία, η νέα τιμή αυτής της ακμής θα είναι ίση με ~p~ XOR ~x~).

Ο Ivan θέλει να αποκτήσει ένα γράφημα στο οποίο κάθε απλός κύκλος είναι καλός. Επίσης, θέλει να το κάνει σε όσο το δυνατόν λιγότερες πράξεις. Προσδιορίστε τον ελάχιστο δυνατό αριθμό πράξεων μετά από τις οποίες κάθε απλός κύκλος είναι καλός και εκτυπώστε τις. Μπορεί να αποδειχθεί ότι είναι πάντα δυνατό να ικανοποιηθούν οι απαιτήσεις του Ivan με μια συγκεκριμένη σειρά πράξεων.

Είσοδος

Η πρώτη γραμμή περιέχει δύο θετικούς ακέραιους αριθμούς ~N~ και ~M~ ~(1 \le N, M \le 100\,000)~, τον αριθμό των κόμβων και τον αριθμό των ακμών.
Στην i-οστή από τις ακόλουθες ~M~ γραμμές υπάρχει μια περιγραφή της i-οστής ακμής: τρεις ακέραιοι αριθμοί ~a_i~, ~b_i~, ~p_i~ ~(1 \le a_i, b_i \le N, a_i \ne b_i, 0 \le p_i \le 10^9)~, οι κόμβοι που συνδέονται με την i-οστή ακμή και η τιμή της ακμής. Το γράφημα είναι συνδεδεμένο και όλες οι ακμές είναι διαφορετικές.

Έξοδος

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

• ο πρώτος αριθμός στη σειρά είναι ο αριθμός ~x~ από την πράξη.
• ο δεύτερος αριθμός είναι ο ~B~, ο αριθμός των επιλεγμένων γεφυρών.
• μετά ακολουθούν ~B~ αριθμοί,​οι ~E_i~ ~(1 \le E_i \le M)~, που υποδεικνύουν τις τιμές των επιλεγμένων ακμών με αύξουσα σειρά.

Όλοι οι αριθμοί στην έξοδο πρέπει να είναι μικρότεροι ή ίσοι του ~2\,\cdot10\,10^9~.

Βαθμολογία

Σε παραδείγματα αξίας 20% των συνολικών πόντων, ο ελάχιστος αριθμός απαιτούμενων πράξεων θα είναι ίσος με 1.
Σε παραδείγματα αξίας επιπλέον 40% των συνολικών πόντων όλοι οι αριθμοί εισόδου θα είναι μικρότεροι ή ίσοι του ~10^6~.

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

input

4 4
1 2 10
2 3 9
3 4 8
4 1 7

output

1
12 3 1 2 3

input

2 1
1 2 3

output

0

input

6 8
1 2 6
2 3 1
3 5 6
3 1 5
4 5 0
3 6 0
4 2 8
4 1 1

output

2
2 2 4 6
15 1 7

Επεξήγηση των παραδειγμάτων:

Στο πρώτο παράδειγμα, το αρχικό γράφημα δίνεται στην εικόνα αριστερά, παρακάτω, και το τελικό γράφημα (μετά την εφαρμογή της XOR στις τρεις πρώτες αμές με 12), δίνεται στην εικόνα αριστερά. Ο μοναδικός κύκλος στο γράφημα είναι καλός επειδή η XOR των ακμών του είναι 0.

Στο δεύτερο παράδειγμα, δεν υπάρχει κύκλος, επομένως ο ισχυρισμός "κάθε απλός κύκλος είναι καλός" δεν πληρείται. Αυτό συμβαίνει γιατί ο αριθμός των απαιτούμενων πράξεων είναι 0.