Trong tương lai xa, thực phẩm được vận chuyển giữa các hành tinh thông qua các tuyến đường thương mại một chiều. Mỗi tuyến đường kết nối trực tiếp hai hành tinh và có thời gian vận chuyển đã biết.

Hiệp hội thương nhân có kế hoạch bổ sung một số tuyến đường mới sử dụng công nghệ được phát hiện gần đây – du hành siêu không gian. Du hành qua siêu không gian cũng là một chiều. Vì nó vẫn đang trong giai đoạn thử nghiệm nên thời gian du hành siêu không gian vẫn chưa được xác định, tuy nhiên người ta biết rằng nó không phụ thuộc vào khoảng cách giữa các hành tinh, vì vậy mỗi tuyến đường siêu không gian sẽ mất một khoảng thời gian bằng nhau để đi qua.

Hình ảnh bên dưới là ví dụ về ba hành tinh được kết nối với nhau với thời gian di chuyển được hiển thị. Các hành tinh được gắn nhãn bằng các số nguyên dương và thời gian di chuyển siêu không gian được biểu thị bằng “~x~” (hình ảnh tương ứng với ví dụ đầu vào thứ hai):

Thời gian vận chuyển được tính bằng ngày và luôn là số nguyên dương. Hiệp hội thương nhân mong muốn phân tích hậu quả của việc giới thiệu các tuyến đường mới: đối với hai hành tinh ~A~ và ~B~, họ muốn biết tất cả các giá trị có thể có của tổng thời gian vận chuyển ngắn nhất từ ~A~ đến ~B~, với tất cả các giá trị có thể có của x. Ví dụ: trong tình huống trên, hành trình ngắn nhất từ hành tinh 2 đến hành tinh 1 có thể mất 5 (nếu ~x ≥ 5~), 4, 3, 2 hoặc 1 ngày (nếu ~x < 5~).

Input

• Dòng đầu tiên chứa hai số nguyên ~P~ và ~R~, lần lượt là số lượng hành tinh và số lượng tuyến đường ~(1 \le P \le 500, 0 \le R \le 10 000)~.
• Mỗi ~R~ dòng tiếp theo chứa hai số nguyên ~C~ và ~D~, nhãn hành tinh ~(1 ≤ C, D ≤ P, C ≠ D)~ và ~T~, thời gian di chuyển từ ~C~ đến ~D~. Đối với các tuyến đường thông thường, ~T~ là một số nguyên ~( 1 ≤ T \le 1 000 000)~ và đối với các tuyến siêu không gian, ~T~ là ký tự “~x~”. Nhiều đường có thể tồn tại giữa hai hành tinh giống nhau.
• Dòng tiếp theo chứa số nguyên ~Q~, số lượng truy vấn ~(1 \le Q \le 10)~.
• Mỗi dòng ~Q~ sau đây chứa hai số nguyên ~A~ và ~B~, nhãn hành tinh ~(A ≠ B)~ thể hiện truy vấn của hiệp hội thương nhân: “các giá trị có thể có của thời gian vận chuyển đường đi ngắn nhất từ ~A~ đến ~B~ là gì?”.

Output

• Đầu ra phải chứa ~Q~ hàng, mỗi hàng một truy vấn.
• Mỗi hàng phải chứa hai số nguyên: số lượng các giá trị khác nhau và tổng của chúng. Nếu số lượng giá trị khác nhau không bị giới hạn, chỉ xuất "inf" trong hàng đó. Nếu không có đường đi từ ~A~ đến ~B~ thì số giá trị khác nhau và tổng của chúng bằng ~0~.

Scoring

• Nếu kết quả đầu ra sai nhưng số đầu tiên ở mỗi hàng ~Q~ đúng thì lời giải sẽ được thưởng 50% số điểm cho trường hợp kiểm thử đó. Lưu ý: Đầu ra phải chứa cả hai số trong mỗi hàng trong đó số lượng giá trị được giới hạn để đủ điều kiện. Trong dữ liệu thử nghiệm có tổng điểm là 50, các ràng buộc sau giữ nguyên: ~P \le 30, R \le 300~ và ~T \le 50~.

Sample Input 1

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

Sample Output 1

0 0 
inf
3 17

Sample Input 2

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

Sample Output 2

inf
5 65
15 185
5 15
inf
1 10

Làm rõ ví dụ đầu tiên:

1. Không có đường đi nào có thể từ ~2~ đến ~1~.
2. Với bất kỳ số nguyên dương ~x~ nào, đường đi ngắn nhất từ ~1~ đến ~3~ mất gấp đôi thời gian, vì vậy nghiệm là "inf".
3. Đường đi ngắn nhất từ ~1~ đến ~4~ có thể mất ~3~ (với ~x = 1~), ~6~ (với ~x = 2~) hoặc 8 (với ~x >= 3~) thời gian. ~3+6+8=17~