Hiperprostor

Στο μακρινό μέλλον, τα τρόφιμα μεταφέρονται μεταξύ πλανητών μέσω μονόδρομων εμπορικών οδών. Κάθε διαδρομή συνδέει απευθείας δύο πλανήτες και έχει γνωστό χρόνο διέλευσης.
Η συντεχνία εμπόρων σχεδιάζει να προσθέσει μερικές νέες διαδρομές χρησιμοποιώντας μια τεχνολογία που ανακαλύφθηκε πρόσφατα - ταξίδι μέσω υπερδιαστήματος. Το ταξίδι μέσω του υπερδιαστήματος είναι επίσης μονής κατεύθυνσης. Δεδομένου ότι είναι ακόμα πειραματικό, ο χρόνος του υπερδιαστημικού ταξιδιού δεν είναι ακόμη γνωστός, ωστόσο είναι γνωστό ότι δεν εξαρτάται από τις αποστάσεις μεταξύ των πλανητών, οπότε η κάθεμία διαδρομή υπερδιαστήματος θα χρειαστεί ίσο χρόνο για να διασχιστεί.
Η παρακάτω εικόνα δείχνει ένα παράδειγμα τριών διασυνδεδεμένων πλανητών με χρόνους διέλευσης. Οι πλανήτες επισημαίνονται με θετικούς ακέραιους αριθμούς και ο χρόνος ταξιδιού μέσω υπερδιαστήματος συμβολίζεται με "~x~" (η εικόνα αντιστοιχεί στο δεύτερο παράδειγμα):

Ο χρόνος διέλευσης μετριέται σε ημέρες και είναι πάντα θετικός ακέραιος.
Η συντεχνία εμπόρων επιθυμεί να αναλύσει τις συνέπειες της εισαγωγής των νέων δρομολογίων: για κάποιους δύο πλανήτες ~A~ και ~B~, θέλουν να μάθουν ποιες είναι όλες οι πιθανές τιμές του συνολικού χρόνου διέλευσης της συντομότερης διαδρομής από το ~A~ έως το ~B~, για όλες τις πιθανές τιμές του ~x~. Για παράδειγμα, στην παραπάνω κατάσταση, η συντομότερη διαδρομή από τον πλανήτη ~2~ στον πλανήτη ~1~ θα μπορούσε να πάρει ~5~ (αν ~x \ge 5~), ~4~, ~3~, ~2~ ή ~1~ ημέρα (αν ~x < 5~).

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τους δύο ακέραιους αριθμούς ~P~ και ~R~, τον αριθμό των διαδρομών και τον αριθμό των διαδρομές, αντίστοιχα ~(1 \le P \le 500,\,0 \le R \le 10\,000)~.
Κάθε μία από τις ακόλουθες γραμμές ~R~ περιέχει δύο ακέραιους αριθμούς ~C~ και ~D~, με τα ονόματα των πλανητών ~(1 \le C, D \le P, C \neq D)~, και ~T~, ο χρόνος ταξιδιού από το ~C~ στο ~D~. Για συμβατικές διαδρομές, το ~T~ είναι ένας ακέραιος αριθμός ~(1 \le T \le 1\,000\,000)~ και για διαδρομές υπερδιαστήματος, ~T~ είναι ο χαρακτήρας "~x~". Πολλαπλές γραμμές μπορεί να υπάρχουν ανάμεσα στους ίδιους δύο πλανήτες. Η ακόλουθη γραμμή περιέχει τον ακέραιο ~Q~, τον αριθμό των ερωτημάτων ~(1 \le Q \le 10)~.
Κάθε μία από τις ακόλουθες γραμμές ~Q~ περιέχει δύο ακέραιους αριθμούς ~A~ και ~B~, με τις ετικέτες του πλανήτη ~(A \neq B)~ να αντιπροσωπεύουν ένα ερώτηση από τη συντεχνία εμπόρων: "ποιες είναι οι πιθανές τιμές του συντομότερου χρόνου διέλευσης από το ~A~ στο ~B~;".

Έξοδος

Η έξοδος πρέπει να περιέχει ~Q~ σειρές, μία ανά ερώτημα.
Κάθε σειρά πρέπει να περιέχει δύο ακέραιους: τον αριθμό των διαφορετικών τιμών και το άθροισμά τους. Αν ο αριθμός των διαφορετικών τιμών είναι απεριόριστος, η έξοδος είναι μόνο "~inf~" σε αυτήν τη σειρά. Εάν δεν υπάρχει μονοπάτι από το ~A~ στο ~B~, το αριθμός διαφορετικών τιμών και το άθροισμά τους είναι ~0~.

Βαθμολογία

Εάν η έξοδος είναι λανθασμένη, αλλά ο πρώτος αριθμός σε κάθε γραμμή Q είναι σωστός, η λύση θα πάρει το ~50~ % των βαθμών για τη συγκεκριμένη περίπτωση. Σημείωση: Η έξοδος πρέπει να περιέχει και τους δύο αριθμούς σε κάθε σειρά όπου ο αριθμός των τιμών είναι περιορισμένος για να πληροί τις προϋποθέσεις.
Στα αρχεία ελέγχου συνολικής αξίας ~50~ βαθμών, ισχύουν οι ακόλουθοι περιορισμοί: ~P \le 30,\,R \le 300~ και ~T \le 50~.

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

input

4 4
1 2 x
2 3 x
3 4 x
1 4 8
3
2 1
1 3
1 4

output

0 0
inf
3 17

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

1. Δεν υπάρχει δυνατό μονοπάτι από το ~2~ στο ~1~.
2. Για κάθε θετικό ακέραιο ~x~, το μικρότερο μονοπάτι από το ~1~ στο ~3~ παίρνει ~2x~ χρόνο, έτσι η λύση είναι "~inf~".
3. Το μικρότερο μονοπάτι από το ~1~ στο ~4~ μπορεί να πάρει ~3~ (για ~x = 1~), ~6~ (για ~x = 2~) ή ~8~ (για ~x \ge 3)~ χρόνο. ~3 + 6 + 8 = 17~

---

input

3 5
3 2 x
2 1 x
2 1 5
1 3 10
3 1 20
6
1 2
2 3
3 1
2 1
3 2
1 3

output

inf
5 65
15 185
5 15
inf
1 10

---