Treasure Hunt

Ο Perry ο Πειρατής ταξιδεύει στις επτά θάλασσες! Διαθέτει έναν χάρτη που αποτελείται από ~N~ νησιά, τα οποία συνδέονται μέσω ενός δικτύου ~M~ θαλάσσιων διαδρομών. Η ~i~-οστή θαλάσσια διαδρομή συνδέει τα νησιά ~a_i~ και ~b_i~ και το κόστος διέλευσής της είναι ~c_i~ νομίσματα, ανεξάρτητα από την κατεύθυνση. Όπως αποδεικνύεται, η αντιμετώπιση θαλάσσιων τεράτων μπορεί να είναι αρκετά δαπανηρή.

Αναζητώντας την επόμενη μεγάλη λεία του, ο Perry έχει εξερευνήσει καθένα από τα ~N~ νησιά και έχει διαπιστώσει ότι το ~i~-οστό νησί περιέχει ένα σεντούκι θησαυρού με ~v_i~ νομίσματα μέσα.

Απομένει να σχεδιάσει το επόμενο ταξίδι του. Αποφασίζει ότι θα διασχίσει μια διαδρομή από θαλάσσιες οδούς, η οποία μπορεί να είναι και κενή, ξεκινώντας από το νησί ~x~ και καταλήγοντας στο νησί ~y~. Στο τέλος του ταξιδιού του, θα ανοίξει το σεντούκι στο νησί ~y~ και θα συλλέξει τη λεία που κέρδισε επάξια.

Υπάρχει, ωστόσο, ένα μικρό πρόβλημα: ο Perry δεν γνωρίζει σε ποιο νησί βρίσκεται αυτή τη στιγμή! Επομένως, για κάθε πιθανό αρχικό νησί ~x~, θέλει να γνωρίζει τον μέγιστο αριθμό νομισμάτων που μπορεί να κερδίσει από όλα τα ταξίδια που ξεκινούν από το νησί ~x~. Μπορείτε να τον βοηθήσετε να υπολογίσει αυτές τις τιμές;

Μπορείτε να θεωρήσετε ότι ο Perry έχει αρκετά νομίσματα για να διασχίσει οποιαδήποτε διαδρομή επιλέξει. Το μόνο που τον ενδιαφέρει είναι το καθαρό κέρδος από το επόμενο ταξίδι του.

Είσοδος

Η πρώτη γραμμή της εισόδου περιέχει δύο ακέραιους αριθμούς ~N~ και ~M~, χωρισμένους με ένα κενό.

Η δεύτερη γραμμή περιέχει ~N~ ακέραιους αριθμούς ~v_1, v_2, \ldots, v_N~, χωρισμένους με κενά (~0 \le v_i \le 10^9~).

Καθεμία από τις επόμενες ~M~ γραμμές περιέχει τρεις ακέραιους αριθμούς ~a_i~, ~b_i~ (~1 \le a_i, b_i \le N~) και ~c_i~ (~0 \le c_i \le 10^9~), χωρισμένους με κενά.

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

Βαθμολογία

Βαθμοί	Περιορισμοί	Επιπλέον περιορισμοί
5	~1 \le N \le 3000~, ~0 \le M \le 3000~	Κανένας.
5	~1 \le N \le 10^6~, ~0 \le M \le 10^6~	Για κάθε ~i~, ισχύει είτε ~c_i = 0~ είτε ~c_i = 10^9~.
7	~1 \le N \le 10^6~, ~0 \le M \le 10^6~	Υπάρχει ακριβώς μία διαδρομή από θαλάσσιες οδούς μεταξύ οποιουδήποτε ζεύγους νησιών.
8	~1 \le N \le 10^6~, ~0 \le M \le 10^6~	Κανένας πρόσθετος περιορισμός.

Έξοδος

Να εκτυπώσετε ~N~ γραμμές, όπου η ~x~-οστή γραμμή περιέχει το μέγιστο δυνατό καθαρό κέρδος, σε νομίσματα, από οποιοδήποτε ταξίδι ξεκινά από το νησί ~x~.

Παράδειγμα

input

4 5
6 5 9 2
1 2 0
3 2 3
4 3 6
1 3 5
2 4 2

output

6
6
9
4

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

Για το πρώτο και το τρίτο νησί, η καλύτερη επιλογή είναι να παραμείνει ο Perry στο ίδιο το νησί και να ανοίξει το σεντούκι εκεί.

Για το δεύτερο νησί, ο Perry μπορεί να ταξιδέψει στο πρώτο νησί και να ανοίξει εκεί το σεντούκι. Αυτό αποφέρει καθαρό κέρδος ~6 - 0 = 6~ νομισμάτων και είναι το καλύτερο δυνατό αποτέλεσμα.

Για το τέταρτο νησί, ο Perry μπορεί να ταξιδέψει πρώτα στο δεύτερο νησί και στη συνέχεια στο τρίτο, όπου θα ανοίξει το σεντούκι. Το καθαρό κέρδος από αυτό το ταξίδι είναι ~9 - 2 - 3 = 4~ νομίσματα, και είναι το καλύτερο δυνατό αποτέλεσμα.