Kamp

Σε ένα συγκεκριμένο πλημμυρισμένο χωριό, ένας μυστικός υπεράνθρωπος ανθρωπιστικός καταυλισμός ανοίγει τη στιγμή που μιλάμε. Το χωριό αποτελείται από ~N~ σπίτια που σημειώνονται με ακέραιους αριθμούς από το ~1~ έως το ~N~. Τα σπίτια συνδέονται μεταξύ τους με ~N-1~ δρόμους έτσι ώστε να υπάρχει ένας μοναδικός τρόπος μεταξύ κάθε δύο σπιτιών. Για κάθε δρόμο, γνωρίζουμε τον χρόνο που χρειάζεται για να τον περάσει ένα φορτηγό. Ο καταυλισμός πρέπει να στηθεί στον κήπο κάποιου σπιτιού, αλλά ο διευθυντής του καταυλισμού δεν έχει αποφασίσει ακόμα ποιο σπίτι θα είναι.

Ο Mirko έχει οριστεί ως οδηγός. Η δουλειά του είναι να οδηγεί ομάδες εθελοντών με το σούπερ φορτηγό του από το στρατόπεδο μέχρι το σπίτι όπου αυτή η συγκεκριμένη ομάδα πρόκειται να εργαστεί. Το βαν του είναι σούπερ γιατί όλες οι ομάδες ταυτόχρονα μπορούν να οδηγήσουν σε αυτό! Συνολικά υπάρχουν ~K~ ομάδες και όλες οι ομάδες πάνε σε διαφορετικό σπίτι.

Όλες οι ~K~ ομάδες επιβιβάζονται αρχικά στο φορτηγό του Mirko και στη συνέχεια τις οδηγεί σε σπίτια με τη σειρά που καθόρισε για τον εαυτό του. Αφού κυκλοφορεί με το αυτοκίνητο σε όλες τις ομάδες, ο Mirko μένει και βοηθά την τελευταία ομάδα (δεν επιστρέφει στον καταυλισμό).

Προκειμένου ο διευθυντής του καταυλισμού να καθορίσει πού θα στήσει τον καταυλισμό, θέλει να γνωρίζει, για κάθε σπίτι, τον ελάχιστο χρόνο που χρειάζεται για να οδηγήσει ο Mirko σε όλες τις ομάδες, εάν αυτό το σπίτι είναι η έδρα. Γράψε ένα πρόγραμμα που θα καθορίζει τους αριθμούς που θέλει να δει το αφεντικό του Μίρκο!

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τους ακέραιους αριθμούς ~N\;(1 \le N \le 500\,000)~ και ~K\;(1 \le K \le N )~.
Καθεμία από τις ακόλουθες γραμμές ~N-1~ περιέχει τους ακέραιους αριθμούς ~A_i ,\;B_i ,\;C_i\;(1 \le A_i,\;B_i \le N,\;1 \le C_i \le 1\,000\,000)~, όπου ~C_i~ είναι ο χρόνος που χρειάζεται για να περάσετε έναν αμφίδρομο δρόμο μεταξύ των σπιτιών ~A_i~ και ~B_i~ .
Κάθε μία από τις ακόλουθες ~K~ γραμμές περιέχει τους ακέραιους αριθμούς που σηματοδοτούν το σπίτι στο οποίο πηγαίνει η ~i~-οστή ομάδα, αντίστοιχα.

Έξοδος

Τυπώστε ~N~ γραμμές. Η ~i~-οστή γραμμή εξόδου πρέπει να περιέχει τους ελάχιστους χρόνους που χρειάζεται ο Mirko για να οδηγήσει σε όλες τις ομάδες, εάν η έδρα του στρατοπέδου βρίσκεται στο ~i~-οστό σπίτι.

Βαθμολογία

Σε περιπτώσεις δοκιμής αξίας 50% των συνολικών πόντων, θα έχει ~ N \le 2\,000~ .

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

input

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

output

5
3
7
2
2

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

Εάν ο Mirko ξεκινήσει από το σπίτι 1, μπορεί να αφήσει εθελοντές στα σπίτια ~1-2-4-2-5~, αντίστοιχα. Εάν ξεκινήσει στο σπίτι 2, η πιθανή σειρά είναι ~2-5-4~.

input

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

output

11
15
10
13
16
15
10