Parkovi

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

Η πόλη αποτελείται από ~n~ γειτονιές που συνδέονται με ~n - 1~ δρόμους συγκεκριμένου μήκους. Υπάρχει ένα μοναδικό μονοπάτι που συνδέει κάθε γειτονιά με οποιαδήποτε άλλη γειτονιά. Με άλλα λόγια, οι γειτονιές και οι δρόμοι σχηματίζουν ένα δέντρο. Ακριβώς ~k~ πάρκα θα πρέπει να χτιστούν σε διαφορετικές γειτονιές ώστε οι άλλες γειτονιές να έχουν το πλησιέστερο πάρκο όσο πιο κοντά τους γίνεται. Πιο συγκεκριμένα, η διοίκηση θέλει να ελαχιστοποιήσει τη μέγιστη απόσταση από μια γειτονιά στο πλησιέστερο πάρκο της.

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

Είσοδος

Η πρώτη γραμμή περιέχει δύο θετικούς ακέραιους ~n~ και ~k\;(1 \le k \le n \le 200\,000)~, τον αριθμό των γειτονιών και τον αριθμό των πάρκων, αντίστοιχα.

Η ~i~-οστή από τις επόμενες ~n - 1~ γραμμές περιέχει θετικούς ακέραιους αριθμούς ~a_i,\;b_i~ και ~w_i\;(1 \le a_i,\;b_i \le n,\;1 \le w_i \le 10^9)~, που υποδηλώνει ότι οι γειτονιές με την ένδειξη ~a_i~ και ~b_i~ συνδέονται με έναν δρόμο μήκους ~w_i~.

Έξοδος

Στην πρώτη γραμμή εκτυπώστε τη μικρότερη δυνατή μέγιστη απόσταση από τη δήλωση του προβλήματος.

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

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	10	~1 \le n \le 20~
2	10	~k = 1~
3	30	~a_i\;=\;i,\;b_i\;=\;i + 1~ για κάθε ~1 \le i \le n - 1~
4	60	Κανένας επιπλέον περιορισμός.

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

input

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

output

8
4 5 8

input

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

output

3
2 4

input

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

output

1
3 4 1 2

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

Εάν τα πάρκα κατασκευάζονταν μόνο στις γειτονιές 3 και 4, η μέγιστη απόσταση δεν θα άλλαζε, αλλά η διοίκηση της πόλης θέλει να χτίσει ακριβώς ~k~ πάρκα, επομένως πρέπει να κατασκευαστούν άλλα δύο κάπου αλλού.