{"code":"cses1672","name":"CSES - Shortest Routes II | Tuyến đường ngắn nhất II","description":"Có $n$ thành phố và $m$ con đường giữa chúng. Nhiệm vụ của bạn là hãy xử lý $q$ truy vấn mà trong đó bạn phải xác định độ dài của tuyến đường ngắn nhất giữa hai thành phố cho trước.\r\n\r\n## Input\r\n\r\n- Dòng đầu vào đầu tiên có ba số nguyên $n$, $m$ và $q$: số lượng thành phố, con đường và truy vấn.\r\n- Sau đó, có $m$ dòng mô tả các con đường. Mỗi dòng có ba số nguyên $a$, $b$ và $c$: có một con đường giữa các thành phố $a$ và $b$ mà độ dài của nó là $c$. Tất cả con đường đều là con đường hai chiều.\r\n- Cuối cùng, có $q$ dòng mô tả các truy vấn. Mỗi dòng có hai số nguyên $a$ và $b$: xác định độ dài của tuyến đường ngắn nhất giữa các thành phố $a$ và $b$.\r\n\r\n## Output\r\n\r\n- In độ dài của tuyến đường ngắn nhất với mỗi truy vấn. Nếu không có tuyến đường nào, in $-1$ thay vào đó.\r\n\r\n## Constraints\r\n\r\n- $1 \\le n \\le 500$\r\n- $1 \\le m \\le n^2$\r\n- $1 \\le q \\le 10^5$\r\n- $1 \\le a,b \\le n$\r\n- $1 \\le c \\le 10^9$\r\n\r\n## Example\r\n\r\n**Sample input**\r\n```\r\n4 3 5\r\n1 2 5\r\n1 3 9\r\n2 3 3\r\n1 2\r\n2 1\r\n1 3\r\n1 4\r\n3 2\r\n```\r\n\r\n**Sample output**\r\n```\r\n5\r\n5\r\n8\r\n-1\r\n3\r\n```","points":1400.0,"partial":true,"time_limit":1.0,"memory_limit":524288,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}