Ceste

Υπάρχει μια χώρα με \(Ν\) πόλεις και \(Μ\) αμφίδρομους δρόμους. Η οδήγηση στο δρόμο ~i~ διαρκεί ​~T_i~ λεπτά και κοστίζει ~C_i~​ kunas (νόμισμα της Κροατίας).

Για να κάνετε την άφιξη στον προορισμό διακοπών όσο το δυνατόν πιο ευχάριστη, θέλετε να την κάνετε όσο το δυνατόν πιο γρήγορη και φθηνή. Πιο συγκεκριμένα, βρίσκεστε στην πόλη 1 και θέλετε να ελαχιστοποιήσετε το γινόμενο των συνολικών χρημάτων που ξοδέψατε και του συνολικού χρόνου (συνολικά, με όλους τους δρόμους που οδηγήσατε) για να φτάσετε σε μια πόλη από την πόλη 1. Για κάθε πόλη (εκτός από την πόλη 1), εξάγετε το απαιτούμενο ελάχιστο γινόμενο ή -1 εάν η πόλη 1 και αυτή η πόλη δεν είναι συνδεδεμένες.

Είσοδος

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

Έξοδος

Πρέπει να εξάγετε ~N-1~ γραμμές. Στη γραμμή ~i~, πληκτρολογήστε το απαιτούμενο ελάχιστο γινόμενο για να φτάσετε στην πόλη \((i​ + 1)\) ή -1 εάν οι πόλεις 1 και \((i​ + 1)\) δεν είναι συνδεδεμένες.

Βαθμολογία

Σε περιπτώσεις δοκιμής αξίας 40% των συνολικών πόντων, θα ισχύει \(1 \le N,\; M,\; T_i,\; C_i​\le 100\).

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

input

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

output

8
3
14

input

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

output

7
6
44

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

Για να φτάσετε στην πόλη 2, πρέπει να οδηγήσετε στον δρόμο 1, για αυτό χρειάζονται 1 λεπτό και 7 κούνα, επομένως το απαιτούμενο γινόμενο είναι 7. Για να φτάσετε στην πόλη 3, πρέπει να οδηγήσετε στον δρόμο 2, για αυτό χρειάζονται 3 λεπτά και 2 κούνα, επομένως το απαιτούμενο γινόμενο είναι 6. Για να φτάσετε στην πόλη 4, πρέπει να οδηγήσετε στους δρόμους 2, 4, 5, με αυτή τη σειρά και για αυτό χρειάζονται συνολικά 11 λεπτά και 4 κούνα, επομένως το απαιτούμενο γινόμενο είναι 44.

input

3 2
1 2 2 5
2 1 3 3

output

9
-1