Barica

Η Barica είναι ένας ασυνήθιστος βάτραχος. Ζει σε μια λίμνη όπου ~N~ φυτά επιπλέουν στην επιφάνεια του νερού. Τα φυτά αριθμούνται από το ~1~ έως το ~N~. Κατά την προβολή από ψηλά, η θέση κάθε φυτού δίνεται από ένα ζεύγος συντεταγμένων. Αυτό που κάνει την Barica ασυνήθιστη είναι ο φόβος της να πηδήξει διαγώνια και προς την αρνητική κατεύθυνση. Πιο συγκεκριμένα, μπορεί να μεταπηδήσει από ένα φυτό στις συντεταγμένες ~(x_1,\;y_1)~ σε ένα άλλο στις συντεταγμένες ~(x_2,\;y_2)~ μόνο εάν:

• ~x_2 > x_1~ και ~y_2 = y_1~, ή
• ~y_2 > y_1~ και ~x_2 = x_1~

Για κάθε φυτό, γνωρίζουμε τον αριθμό των μυγών στην άμεση γειτνίασή του. Η Barica μπορεί να χρησιμοποιήσει τη γρήγορη γλώσσα της για να φάει όλες τις μύγες κοντά στο φυτό στο οποίο βρίσκεται.
Η Barica απορροφά μία μονάδα ενέργειας για κάθε μύγα που τρώει και χρησιμοποιεί ~K~ μονάδες ενέργειας για κάθε άλμα που κάνει. Η Barica δεν μπορεί να κάνει ένα άλμα εάν δεν έχει αρκετές ενεργειακές μονάδες εκ των προτέρων.
Η Barica θέλει να πάει από το φυτό ~1~, στο φυτό ~N~ και να έχει τη μεγαλύτερη δυνατή ποσότητα ενέργειας μετά την άφιξή της. Η Barica αρχικά δεν έχει ενέργεια και πρέπει να συγκεντρώσει ενέργεια για το πρώτο της άλμα από τις μύγες γύρω από το φυτό ~1~.
Βρείτε την ακολουθία των φυτών στα οποία πρέπει να ταξιδέψει η Barica για να πετύχει τον στόχο της.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει δύο ακέραιους ~N~ και ~K\;(2 \le N \le 300\,000,\;1 \le K \le 1\,000)~ που χωρίζονται με ένα κενό.
Καθεμία από τις ακόλουθες ~N~ γραμμές περιέχει τρεις ακέραιους αριθμούς ~X,\;Y~ και ~F\;(0 \le X, Y \le 100\,000,\;0 \le F \le 1\,000)~ οι οποίοι χωρίζονται με κενά, που σημαίνει ότι υπάρχει ένα φυτό σε συντεταγμένες ~(X,\;Y)~ με ~F~ μύγες γύρω του.
Το πρώτο φυτό στην είσοδο είναι το φυτό ~1~, το δεύτερο είναι το φυτό ~2~ κ.λπ.
Κανένα φυτό δεν θα μοιράζεται το ίδιο ζεύγος συντεταγμένων.
Σημείωση: Τα δεδομένα εισόδου θα εγγυηθούν ότι μια ακολουθία πηδημάτων, αν και όχι απαραίτητα μοναδική, θα υπάρχει πάντα.

Έξοδος

Τυπώστε το τελικό επίπεδο ενέργειας στην πρώτη γραμμή.
Τυπώστε έναν ακέραιο αριθμό ~L~, τον αριθμό των φυτών στα οποία πρέπει να ταξιδέψει η Barica, συμπεριλαμβανομένων των φυτών ~1~ και ~N~.
Στις ακόλουθες γραμμές ~L~, τυπώστε την ακολουθία των φυτών στα οποία πρέπει να ταξιδέψει η Barica.

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

input

6 5
1 1 5
2 1 5
1 2 4
2 3 5
3 2 30
3 3 5

output

5
4
1 1
2 1
2 3
3 3

input

8 10
1 1 15
2 2 30
1 2 8
2 1 7
3 2 8
2 3 7
4 2 100
3 3 15

output

36
5
1 1
1 2
2 2
3 2
3 3

input

9 5
5 5 10
6 5 2
7 5 1
5 6 2
6 6 6
7 6 2
5 7 1
6 7 2
7 7 1

output

2
3
5 5
7 5
7 7