Utrka

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

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

Είσοδος

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

Κάθε μία από τις ακόλουθες $M$ γραμμές περιέχει 4 ακέραιους $A_i,B_i,M_i,S_i(1\le A_i,B_i\le N,Ai\ne B_i,0\le S_i,M_i\le {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