{"code":"dulich","name":"Du Lịch Biển Đảo","description":"Hôm nay là chủ nhật, [user:shiba] quyết định ra đảo chơi. \r\n\r\nQuần đảo nơi [user:shiba] chơi có tất cả $n$ đảo, được nối với nhau bằng $m$ con đường một chiều. [user:shiba] quyết định sẽ đi tham quan từ đảo $1$ tới đảo $n$. Con đường thứ $i$ nối hai đảo $u_i$ và $v_i$ với nhau có chi phí là $c_i$. [user:shiba] có siêu năng lực là cải tạo các con đường (yep, ngay lập tức) tuy nhiên khả năng này chỉ có thể sử dụng $k$ lần. Sau khi cải tạo, chi phí của con đường sẽ là $\\lfloor \\frac{c_i}{2} \\rfloor$. Tuy nhiên có một giới hạn là nếu như cậu ấy cải tạo ít nhất một con đường đến đỉnh thứ $u$, thì cậu ấy sẽ không thể cải tạo bất cứ con đường nào đi ra từ đỉnh $u$ đó.\r\n\r\n**Yêu cầu:** Tìm đường đi ngắn nhất từ đảo $1$ tới đảo $n$. Nếu không thể tìm thấy đường đi, in ra `-1`.\r\n\r\n#### Input\r\n\r\n - Dòng thứ nhất chứa ba số nguyên dương $n,m,k$ ($n \\le 10^3, m \\le 10^5, k \\le min(m,500)$).\r\n - $m$ dòng tiếp theo, mỗi dòng chứa ba số nguyên dương $u,v,c$ ($u,v \\le n, c \\le 10^9$).\r\n\r\n#### Output\r\n\r\n - Một số nguyên duy nhất là kết quả bài toán.\r\n\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        5 5 1\r\n        1 2 1\r\n        2 3 1\r\n        3 4 1\r\n        4 5 1\r\n        5 1 1\r\n        ```\r\n    \r\n    ???+ success \"Output\"\r\n        ```sample\r\n        3\r\n        ```","points":1000.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}}