Come Back Quickly

Στη Δημοκρατία του AtCoder, υπάρχουν ~N~ πόλεις που αριθμούνται από το ~1~ έως το ~N~ και ~M~ δρόμοι που αριθμούνται από το ~1~ έως το ~M~. Ο δρόμος ~i~ είναι μονόδρομος από την πόλη ~A_i~ προς την πόλη ~B_i~ και χρειάζονται ~C_i~ λεπτά για να τον διασχίστουμε. Είναι πιθανό, ~A_i = B_i~, και μπορεί να υπάρχουν πολλοί δρόμοι που να συνδέουν το ίδιο ζεύγος πόλεων.

Ο Takahashi σκέφτεται να κάνει μια βόλτα στη χώρα. Θα ονομάζουμε έναν περίπατο έγκυρο(valid) όταν περνάει από έναν ή περισσότερους δρόμους και επιστρέφει στην πόλη από την οποία ξεκινάει. Για κάθε πόλη, προσδιορίστε αν υπάρχει έγκυρος περίπατος που ξεκινά από την πόλη αυτή. Επιπλέον, αν η απάντηση είναι θετική, βρείτε τον ελάχιστο χρόνο που απαιτείται για έναν τέτοιο περίπατο.

Περιορισμοί

• ~1 \le N \le 2000~
• ~1 \le M \le 2000~
• ~1 \le A_i \le N~
• ~1 \le B_i \le N~
• ~1 \le C_i \le 10^5~
• Όλες οι τιμές στην είσοδο θα είναι ακέραιοι αριθμοί.
• Time Limit: ~3~ sec.
• Memory Limit: ~1024~ MB

Είσοδος

Η είσοδος θα δίνεται από την τυπική είσοδο και θα έχει την ακόλουθη μορφή:

N M

A1​ B1​ C1​

A2​ B2​ C2​

A3​ B3​ C3​

⋮

AM​ BM​ CM​

Έξοδος

Εκτυπώστε ~N~ γραμμές. Η ~i~-οστή γραμμή ~(1 \le i \le N)~ πρέπει να περιέχει τα εξής:

• εάν υπάρχει έγκυρος περίπατος που ξεκινά από την πόλη ~i~, τον ελάχιστο χρόνο που απαιτείται για έναν τέτοιο περίπατο,
• διαφορετικά, ~-1~.

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

1ο

input

4 4
1 2 5
2 3 10
3 1 15
4 3 20

output

30
30
30
-1

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

Μέσω των δρόμων ~1~, ~2~, ~3~, οι πόλεις ~1~, ~2~, ~3~ σχηματίζουν έναν δακτύλιο που χρειάζεται ~30~ λεπτά για να διασχιστεί. Από την πόλη ~4~, μπορούμε να πάμε στις πόλεις ~1~, ~2~, ~3~, αλλά μετά δεν μπορούμε να επιστρέψουμε στην πόλη ~4~.

2ο

input

4 6
1 2 5
1 3 10
2 4 5
3 4 10
4 1 10
1 1 10

output

10
20
30
20

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

Μπορεί να υπάρχει δρόμος τέτοιος που ~A_i = B_i~. Εδώ, μπορούμε να χρησιμοποιήσουμε τον δρόμο ~6~ για να αναχωρήσουμε από την πόλη ~1~ και να επιστρέψουμε στην πόλη αυτή.

3ο

input

4 7
1 2 10
2 3 30
1 4 15
3 4 25
3 4 20
4 3 20
4 3 30

output

-1
-1
40
40

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

Προσέξτε ότι μπορεί να υπάρχουν πολλοί δρόμοι που να συνδέουν το ίδιο ζεύγος πόλεων.