Travelling Merchant

Ένας έμπορος θέλει να κάνει μια δουλειά ταξιδεύοντας μεταξύ πόλεων, μετακινώντας αγαθά από μία πόλη σε άλλη με αντάλλαγμα ένα κέρδος. Υπάρχουν ~N~ πόλεις και ~M~ εμπορικές οδοί μεταξύ τους.

Η ~i~-οστη εμπορική οδός επιτρέπει στον έμπορο να ταξιδέψει από την πόλη ~a_i~ στην πόλη ~b_i~ (μόνο με αυτή την κατεύθυνση). Προκειμένου να ακολουθήσει αυτή τη διαδρομή, ο έμπορος πρέπει να έχει ήδη τουλάχιστον ~r_i~ μονάδες χρημάτων. Αφού ακολουθήσει αυτή τη διαδρομή, το συνολικό ποσό χρημάτων που έχει ο έμπορος θα αυξηθεί κατά ~p_i~ μονάδες, με την εγγύηση ότι ~p_i~ ~\ge~ ~0~.

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

Είσοδος

Η πρώτη γραμμή περιέχει δύο ακέραιους ~N~ και ~M~ (~2~ ~\le~ ~N~, ~M~ ~\le~ ~200\,000~).

Η ~i~-οστη από τις επόμενες ~M~ γραμμές περιέχει τους τέσσερις ακέραιους ~a_i~, ~b_i~, ~r_i~ και ~p_i~ (~1~ ~\le~ ~a_i~, ~b_i~ ~\le~ ~N~, ~a_i~ ~ne~ ~b_i~, ~0~ ~\le~ ~r_i~,~p_i~ ~\le~ ~10^9~). Σημειώστε ότι μπορεί να υπάρχει οποιοσδήποτε αριθμός διαδρομών μεταξύ ενός ζεύγους πόλεων.

Βαθμολογία

Για ~4~ από τους ~25~ διαθέσιμους βαθμούς, ~N~,~M~ ~\le~ ~2\,000~.

Για επιπλέον ~5~ από τους ~25~ διαθέσιμους βαθμούς, ~p_i~ ~=~ ~0~ για κάθε ~i~.

Έξοδος

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

Παράδειγμα

input

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

output

2 3 3 1 -1

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

Ξεκινώντας από την πόλη ~2~ με ~3~ μονάδες χρημάτων, ο έμπορος μπορεί να κινείται μεταξύ των πόλεων ~2~, ~1~ και ~3~