{"code":"cses1196","name":"CSES - Flight Routes | Lộ trình bay","description":"Nhiệm vụ của bạn là tìm $k$ lộ trình bay ngắn nhất từ Syrjälä đến Metsälä. Một lộ trình có thể đi qua một thành phố vài lần.\r\n\r\nLưu ý rằng có thể có một số lộ trình với cùng một mức giá và mỗi lộ trình nên được xét (xem ví dụ).\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à $k$: số lượng thành phố, chuyến bay, và tham số $k$. Các thành phố được đánh số $1, 2, \\ldots, n$. Thành phố $1$ là Syrjälä, và thành phố $n$ là Metsälä.\r\n- Sau này, có $m$ dòng mô tả các chuyến bay. Mỗi dòng có ba số nguyên $a$, $b$, và $c$: chuyến bay bắt đầu tại thành phố $a$, kết thúc tại thành phố $b$, và giá của nó là $c$. Tất cả các chuyến bay đều là chuyến bay một chiều.\r\n- Bạn có thể giả định rằng có ít nhất $k$ lộ trình phân biệt từ Syrjälä đến Metsälä.\r\n\r\n## Output\r\n\r\n- In $k$ số nguyên: giá của $k$ tuyến đường rẻ nhất được sắp xếp theo giá của chúng.\r\n\r\n## Constraints\r\n\r\n- $2 \\le n \\le 10^5$\r\n- $1 \\le m \\le 2 \\cdot 10^5$\r\n- $1 \\le a,b \\le n$\r\n- $1 \\le c \\le 10^9$\r\n- $1 \\le k \\le 10$\r\n\r\n## Example\r\n\r\n**Sample input**\r\n```\r\n4 6 3\r\n1 2 1\r\n1 3 3\r\n2 3 2\r\n2 4 6\r\n3 2 8\r\n3 4 1\r\n```\r\n\r\n**Sample output**\r\n```\r\n4 4 7\r\n```\r\n\r\n## Note\r\n\r\nCác lộ trình rẻ nhất là $1 \\rightarrow 3 \\rightarrow 4$ (giá là $4$), $1 \\rightarrow 2 \\rightarrow 3 \\rightarrow 4$ (giá là $4$) và $1 \\rightarrow 2 \\rightarrow 4$ (giá là $7$).","points":1700.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}}