Cho đơn đồ thị G=(V,E) có hướng có trọng số ở cạnh và không có khuyên, hãy tìm đường đi ngắn nhất giữa các cặp đỉnh

Input

Dòng đầu gồm 3 số \(n, m, q\) trong đó \(n\) là số đỉnh của đồ thị, \(m\) là số cung (đường đi 1 chiều) và \(q\) là số truy vấn \((1 <n \leq 200; 1 \leq m \leq n*(n-1); 1 \leq q \leq 10^5)\)

Tiếp theo gồm \(m\) dòng mỗi dòng gồm 3 giá trị \(u,v,w\) thể hiện cung \((u,v)\) có trọng số \(w\) \((1 \leq u,v \leq u)\), \(u\) khác \(v\); \(1 \leq w \leq 10^4\)

Cuối cùng gồm \(q\) truy vấn mỗi truy vấn trên 1 dòng gồm hai đỉnh \((u,v)\) \((1 \leq u,v \leq u)\), \(u\) khác \(v\) cần tính độ dài đường đi ngắn nhất

Output

Với mỗi truy vấn xuất ra trên một dòng độ dài đường đi ngắn nhất từ đỉnh \(u\) đến đỉnh \(v\) trong trường hợp không có đường đi thì xuất ra \(-1\)

Ví dụ

Input

6 10 5
1 2 16
1 4 14
3 1 7
2 3 7
3 4 2
4 5 8
3 5 12
2 6 4
3 6 2
5 6 5
1 6
6 3
3 5
4 2
2 5

Output

20
-1
10
-1
17