Tập viết

Roger đang tập viết với danh sách gồm ~n~ từ phân biệt và ~m~ mối quan hệ giữa chúng. Mỗi mối quan hệ được biểu thị bởi ba số nguyên ~a~, ~b~ và ~t~, biểu thị rằng sau khi viết từ ~a~, cần đợi ~t~ giây mới có thể viết tiếp từ ~b~.

Bố mẹ của Roger đặt ra ~q~ thách thức, yêu cầu viết một câu bắt đầu bằng từ ~s~ và kết thúc bằng từ ~e~. Hãy giúp Roger xác định thời gian ngắn nhất để hoàn thành mỗi thử thách.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ ~(2 \le n \le 1000; \; 1 \le m \le 1000)~.
• ~m~ dòng tiếp theo, mỗi dòng chứa hai từ ~a~, ~b~ chỉ chứa ký tự chữ cái in thường (mỗi từ chứa tối đa ~20~ ký tự) và một số nguyên ~t~ ~(1 \le t \le 10^9)~. Dữ liệu đảm bảo mỗi từ trong danh sách xuất hiện trong ít nhất một mối quan hệ.
• Dòng tiếp theo chứa số nguyên ~q~ ~(1 \le q \le 1000)~.
• ~q~ dòng tiếp theo, mỗi dòng chứa hai từ ~s~ và ~e~ biểu thị thử thách. Dữ liệu đảm bảo hai từ đã cho nằm trong danh sách.

Output

• Với mỗi thử thách, in ra trên một dòng là thời gian ngắn nhất để hoàn thành. Nếu không thể hoàn thành, in ra ~\text{Roger}~.

Samples

3 2
novak goat 1
goat simulator 3
2
novak simulator
simulator goat

4
Roger

3 3
kile legend 4
legend beer 5
beer kile 6
2
kile beer
legend kile

9
11

4 5
rafael me 5
me ow 6
ow ausopenfinal 2012
ausopenfinal me 2
rafael ausopenfinal 2
3
rafael me
me rafael
ow me

4
Roger
2014

Scoring

• Subtask ~1~ với ~30\%~ số điểm: ~n \le 10~
• Subtask ~2~ với ~30\%~ số điểm: ~n \le 100~
• Subtask ~3~ với ~40\%~ số điểm: Không còn ràng buộc gì thêm

Clarification

Trong ví dụ đầu tiên, ở thử thách thứ nhất, Roger bắt đầu với từ ~\text{novak}~, sau ~1~ giây viết tiếp từ ~\text{goat}~ và sau ~3~ giây viết tiếp từ ~\text{simulator}~. Tổng thời gian để hoàn thành thử thách là ~1+3=4~.