Utrka

Ο Mirko και ο Slavko είναι οι μόνοι δύο διαγωνιζόμενοι στο Grand Prix της Dabrovina Donja, το οποίο οδηγείται μέσα από κοντινά χωριά. Τα χωριά συνδέονται μέσω μονόδρομων, και για κάθε δρόμο ~i~ γνωρίζουμε το ~M_i~ και το ~S_i~, τον χρόνο που απαιτείται για να διασχίσουν ο Μίρκο και ο Σλάβκο αυτόν τον δρόμο. Ο ίδιος ο αγώνας είναι κυκλικός (δηλαδή ξεκινά και τελειώνει από το ίδιο χωριό), αλλά η ίδια η διαδρομή δεν έχει ακόμη καθοριστεί.

Ο Mirko έχει δωροδοκήσει τους διοργανωτές του αγώνα, ώστε να επιλέξουν μια διαδρομή υπέρ του. Συγκεκριμένα, οι διοργανωτές θα επιλέξουν τη συντομότερη διαδρομή (που περιέχει τον ελάχιστο αριθμό δρόμων) έτσι ώστε ο Mirko να είναι αυστηρά ταχύτερος από τον Slavko σε αυτή τη διαδρομή. Αν, τυχαία, υπάρχουν πολλές τέτοιες διαδρομές, οι διοργανωτές επιλέγουν αυτή όπου ο Mirko αποκτά το μέγιστο πλεονέκτημα.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει δύο ακέραιους αριθμούς ~N,\;M\;(2 \leq N \leq 300,\;2 \leq M \leq N(N-1))~, τον αριθμό των χωριών και τον αριθμό των συνδεόμενων δρόμων.

Κάθε μία από τις ακόλουθες ~M~ γραμμές περιέχει 4 ακέραιους ~A_i,\;B_i,\;M_i,\;S_i\;(1 \leq A_i,\;B_i \leq N,\;Ai \neq B_i,\;0 \leq S_i,\;M_i \leq 10^6)~. Το αρχικό και τελικό χωριό του i-οστού δρόμου, ο χρόνος που απαιτείται για τον Μίρκο και ο χρόνος που απαιτείται για να διασχίσει ο Slavko αυτόν τον δρόμο, αντίστοιχα. Δεν θα υπάρχουν δύο διαφορετικοί δρόμοι που συνδέουν το ίδιο ζευγάρι χωριών προς την ίδια κατεύθυνση.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει δύο ακέραιους αριθμούς: τη συντομότερη δυνατή διαδρομή (με τον ελάχιστο αριθμό δρόμων) έτσι ώστε να κερδίζει ο Mirko και το μέγιστο πλεονέκτημα που μπορεί να κερδίσει ο Mirko σε μια διαδρομή με το μικρότερο μήκος.

Σημείωση: Τα δεδομένα εισόδου θα είναι τέτοια ώστε να υπάρχει πάντα μια διαδρομή που πληροί τις προϋποθέσεις από το κείμενο.

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

input

3 4
1 2 3 0
2 3 3 0
3 1 0 100
2 1 0 4

output

2 1

input

5 7
1 2 4 1
2 3 5 1
3 1 1 6
1 3 15 5
2 4 7 5
4 5 1 4
5 3 1 0

output

5 2