{"code":"23on2c23","name":"Rút Tiền","description":"Sau một ngày đi chơi siêu cháy ở lễ hội cosplay Nubustes, [user:shiba] và [user:\\_minhduc] phải trở về nhà của mình để còn tiếp tục làm việc và viết đề, sinh test cho các LQDOJ-er :Đ\r\n\r\nGiữa hai tỉnh có tất cả $n$ địa điểm và có $m$ con đường nối các điểm này với nhau. Hiện tại, lễ hội Nubustes đang diễn ra tại điểm $1$, [user:\\_minhduc] và [user:shiba] cần phải về tới nhà tại điểm $n$. Các con đường này đều là đường hai chiều, con đường thứ $i$ nối hai địa điểm $u_{i}$ và $v_{i}$ với nhau. Có hai cách đi trong một con đường:\r\n\r\n - Đi bằng xe máy của hai người và tốn chi phí bằng một lượng $c_{i}$ đồng.\r\n - Dắt xe máy lên một chiếc xe buýt và phải trả cho tài xế chi phí bằng một lượng $d_{i}$ đồng.\r\n\r\nTuy nhiên, mỗi lần đổi giữa đi xe máy và đi xe buýt, hai người đều mất chi phí bằng $1$. Ví của hai người có thể chứa tối đa $k$ đồng. Ban đầu, tại lễ hội Nubustes họ đã có đầy ví tiền. Ngoài ra, ở mỗi điểm đều có ngân hàng, ngân hàng cho phép rút một số tiền bất kì, tuy nhiên cứ với mỗi $100$ đồng bạn rút bạn phải trả chi phí là $1$ đồng cho ngân hàng, ngoài ra nếu bạn rút một phần tiền chưa đạt đên $100$ đồng bạn vẫn sẽ mất $1$ đồng, ví dụ: bạn rút $500$ đồng bạn phải trả cho ngân hàng phí là $5$ đồng, bạn rút $501$ đồng bạn phải trả cho ngân hàng phí là $6$ đồng.\r\n\r\nHỏi chi phí ít nhất để hai người có thể về tới nhà là bao nhiêu?\r\n\r\n#### Input\r\n\r\n - Dòng thứ nhất chứa ba số nguyên dương $n,m$ ($n \\le 10^4$, $m \\le 10^5$).\r\n - $m$ dòng tiếp theo, mỗi dòng chứa bốn số nguyên biểu diễn một con đường ($1 \\le u,v \\le n, 0 \\le c,d \\le 10^3$).\r\n - Dòng cuối cùng chứa số nguyên dương $k$ ($k \\le 10^3$).\r\n - Dữ liệu đảm bảo con đường nào cũng có thể đi được nếu ví tiền của hai người đầy.\r\n\r\n#### Output\r\n\r\n - Một dòng chứa một số nguyên duy nhất là chi phí để di chuyển từ lễ hội Nubustes về đến nhà của [user:\\_minhduc] và [user:shiba].\r\n\r\n#### Scoring\r\n\r\n - Subtask $1$ ($30\\%$ số điểm): $d_{i} = 1000$ với $i = 1,2,3...,m$.\r\n - Subtask $2$ ($70\\%$ số điểm): không có ràng buộc gì thêm.\r\n\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        3 2\r\n        1 2 1 99\r\n        2 3 99 1\r\n        1000\r\n        ```\r\n    \r\n    ???+ success \"Output\"\r\n        ```sample\r\n        3\r\n        ```","points":1500.0,"partial":false,"time_limit":2.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}}