{"code":"nc2_dijkstra_10","name":"Con đường danh lợi","description":"Đất nước ABC có $n$ thành phố và $m$ con đường **một chiều**. Con đường thứ $i$ nối hai thành phố $u_i$ và $v_i$ với nhau, có độ dài $l_i$ và có chi phí $t_i$.\r\n\r\n$H$ là một du khách. Hiện tại, anh đang ở thành phố $1$ và cần đi tới thành phố $n$. Tuy nhiên anh ta chỉ mang đúng $K$ đồng tiền.\r\n\r\nHãy giúp $H$ tính toán lộ trình ngắn nhất từ thành phố $1$ tới $n$ mà chỉ mất tổng chi phí ít hơn hoặc bằng $K$.\r\n\r\n#### Input\r\n- Dòng thứ nhất chứa $2$ số nguyên dương $n, m$.\r\n- Dòng thứ hai chứa số nguyên dương $K$.\r\n- $m$ dòng sau mỗi dòng gồm $4$ số nguyên dương $u_i, v_i, l_i, t_i$ $(1 \\le u, v \\le n, u \\neq v)$, miêu tả con đường nối thành phố $u_i$ với $v_i$ có độ dài $l_i$ và chi phí $t_i$.\r\n\r\n#### Output\r\n- In ra độ dài đường đi ngắn nhất từ $1$ tới $n$ mà tổng chi phí không quá $K$.\r\n- Nếu không có lộ trình nào để đi từ $1$ tới $n$ và tiêu không quá $K$, in ra $-1$.\r\n\r\n#### Constraints\r\n- $1 \\le n \\le 100$.\r\n- $1 \\le m \\le 1000$.\r\n- $1 \\le k \\le 10000$.\r\n- $1 \\le l_i \\le 1000$.\r\n- $0 \\le t_i \\le 1000$.\r\n\r\n#### Subtasks\r\n- Subtask $1$: $1 \\le n,m \\le 20$ (30%)\r\n- Subtask $2$: Không có ràng buộc gì thêm (70%)\r\n\r\n#### Sample Input 1\r\n```text\r\n6 7\r\n5\r\n1 2 2 3\r\n2 4 3 3\r\n3 4 2 4\r\n1 3 4 1\r\n4 6 2 1\r\n3 5 2 0\r\n5 4 3 2\r\n```\r\n\r\n#### Sample Output 1\r\n\r\n```text\r\n11\r\n```\r\n\r\n#### Explanation 1\r\n\r\nĐi theo lộ trình $(1,3,5,4,6)$.\r\n\r\n#### Sample Input 2\r\n\r\n```text\r\n4\r\n4\r\n0\r\n1 4 5 2\r\n1 2 1 0\r\n2 3 1 1\r\n3 4 1 0\r\n```\r\n\r\n#### Sample Output 2\r\n\r\n```text\r\n-1\r\n```\r\n\r\n#### Explanation 2\r\n\r\nKhông có lộ trình nào để đi từ $1$ tới $4$ tiêu không quá $0$.","points":100.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"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}}