{"code":"thmttn23p2","name":"Những chuyến bay","description":"Vào kỷ nguyên mới, thế giới chia thành $n$ quốc gia, tạm đánh số từ $1$ tới $n$. Lúc này, Phong đang ở quốc gia $1$, và Hải đang nghỉ hưu tại quốc gia $n$ và Phong lên kế hoạch đi thăm Hải.\r\n\r\nThời kỳ này mỗi quốc gia chỉ có một sân bay đặt tại thủ đô. Phong có $k$ phiếu voucher của hãng hàng không VA. Hãng VA có $m$ đường bay được đánh số từ $1$ đến $m$, đường bay thứ $i$ đi từ thủ đô của quốc gia $u_i$ tới thủ đô của quốc gia $v_i$, có giá vé là $w_i$. Tuy nhiên, nếu Phong đặt vé cho đường bay thứ $i$ và áp dụng voucher, thì giá vé được áp dụng là $-w_i$. Vì thế, Phong hoàn toàn có thể gặp Hải mà không hề mất đồng nào, thậm chí là được thêm tiền.\r\n\r\n**Lưu ý:**\r\n- Có đường bay đi từ quốc gia $u$ đến quốc gia $v$ không có nghĩa là sẽ có đường bay đi từ quốc gia $v$ đến quốc gia $u$. \r\n- Một đường bay có thể được đi qua nhiều lần, và mỗi lần di chuyển đều phải mua một vé riêng.\r\n- Mỗi phiếu voucher chỉ có hiệu lực trong $1$ lần di chuyển, áp dụng lên duy nhất một vé.\r\n\r\nPhong tìm cách đặt vé của một số chuyến bay, để di chuyển từ thủ đô của quốc gia $1$ tới thủ đô của quốc gia $n$, sao cho số tiền phải bỏ ra là ít nhất. Nói cách khác, giả sử Phong đặt $k$ chuyến bay thứ $f_1, f_2, \\dots, f_k$ $(k \\geq 1)$, với chuyến bay thứ $i$ mua vé của đường bay $f_i$ và giá vé sau khi áp dụng voucher (hoặc không) là $w'_i$ ($w'_i = w_i$ nếu Phong không sử dụng voucher, hoặc $w'_i = -w_i$ nếu Phong sử dụng voucher); thì $v_{f_i} = u_{f_{i+1}} \\ (\\forall 1 \\le i < k)$, $u_{f_1} = 1$, $v_{f_k} = n$ và tổng $w'_1 + w'_2 + \\dots + w'_k$ phải là \\textbf{nhỏ nhất có thể}.\r\n\r\n**Yêu cầu:** Hãy tìm cách đặt vé giúp Phong để anh ta sớm được gặp Hải!\r\n\r\n\r\n#### Input\r\n- Dòng đầu tiên lần lượt chứa ba số nguyên dương $n, m, k$ $(1 \\le n \\le 10^5; 1 \\le m \\le 2 \\times 10^5; 0 \\le k \\le 100)$.\r\n- $m$ dòng sau, dòng thứ $i$ chứa ba số $u_i, v_i, w_i$ $(1 \\le u_i, v_i \\le n; u_i \\neq v_i; 1 \\le w_i \\le 10^9)$.\r\n\r\n#### Output\r\n- In ra một số nguyên duy nhất là kết quả của bài toán. Dữ liệu vào đảm bảo luôn có cách đi từ thủ đô của quốc gia $1$ tới thủ đô của quốc gia $n$ bằng một hoặc nhiều tuyến bay. \r\n\r\n\r\n#### Scoring\r\n- Subtask $1$ ($15$ điểm): $k = 0$\r\n- Subtask $2$ ($21$ điểm): $k = 1$\r\n- Subtask $3$ ($23$ điểm): $e^{u_i} - e^{v_i} < u_i - v_i$ với mọi $1 \\leq i \\leq m$.\r\n- Subtask $4$ ($22$ điểm): $n \\le 1000; m \\le 3000$\r\n- Subtask $5$ ($19$ điểm): Không có ràng buộc gì thêm.\r\n\r\n\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        7 10 1\r\n        1 2 2\r\n        1 5 1\r\n        2 3 1\r\n        3 6 1\r\n        4 3 2\r\n        4 7 2\r\n        5 4 3\r\n        6 4 4\r\n        6 7 3\r\n        4 1 2\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        0\r\n        ```\r\n    ??? warning \"Note\"\r\n        Hình vẽ dưới đây mô tả test ví dụ ở trên. Các cạnh màu vàng thể hiện các đường bay Phong sử dụng để đi từ thủ đô của quốc gia $1$ tới thủ đô của quốc gia $n$. Cạnh nét đứt là đường bay được Phong mua với voucher.\r\n        ![enter image description here][1]\r\n\r\n\r\n  [1]: /media/pagedown-uploads/thmttn23p2.jpg","points":100.0,"partial":true,"time_limit":5.0,"memory_limit":524288,"short_circuit":false,"allowed_languages":[4,34,36,37,11,28,38,39,29,27,35,10,32,33,41,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}