Problem
Đối với Trường học máy tính mùa hè tiếp theo, chúng tôi đã quyết định chuẩn bị các nhóm cho cả học sinh và tất cả giáo viên.
Có thói quen làm những việc quan trọng vào giây phút cuối cùng, nhà thiết kế đã hoàn thành bố cục hai ngày trước khi khai giảng. Sẽ mất thêm một ngày nữa để nhà sản xuất tạo ra những chiếc cốc và dán hình ảnh lên đó. NATO chỉ mất 24 giờ để đưa cốc từ nhà máy đến LKSH.
Đơn đặt hàng 10.000.000 cốc (cụ thể là số lượng ban tổ chức đã đặt), tất nhiên, không thể lấy đi trong một chuyến bay. Tuy nhiên, đối với chuyến bay đầu tiên, tôi muốn mang theo số lượng cốc tối đa. Một chiếc xe tải hạng nặng đã được lệnh vận chuyển. Nhưng có một lưu ý: trên một số con đường có giới hạn về trọng lượng của ô tô. Do đó, nếu ô tô chất đầy cốc đến tận mắt thì có thể không sử dụng được đường ngắn nhất mà phải đi đường vòng. Thậm chí có thể xảy ra trường hợp vì điều này mà xe tải sẽ không kịp đến trại và điều này không được phép xảy ra. Vậy có thể chất bao nhiêu cốc lên xe để có thời gian chở số hàng có giá trị này đúng giờ và không vi phạm luật đi đường?
Đầu vào
Dòng đầu tiên chứa các số n (1≤n≤500) và m - số nút trong bản đồ đường và số đường tương ứng. m dòng tiếp theo chứa thông tin về các con đường. Mỗi con đường được mô tả trên một dòng riêng biệt như sau. Đầu tiên, số lượng các điểm giao nhau được kết nối bởi con đường này được đưa ra, sau đó là thời gian cần thiết để di chuyển dọc theo con đường này và cuối cùng là trọng lượng tối đa của ô tô được phép lái trên con đường này. Được biết, tất cả các con đường đều nối các điểm khác nhau và đối với mỗi cặp điểm, có nhiều nhất một con đường nối trực tiếp chúng. Tất cả các số được phân tách bằng một hoặc nhiều dấu cách.
Các điểm nút được đánh số từ 1 đến n. Đồng thời, nhà máy sản xuất cốc có số 1 và LKSH - số n. Thời gian di chuyển trên đường được tính bằng phút và không vượt quá 1440 (24 giờ). Giới hạn khối lượng được tính bằng gam và không vượt quá một tỷ. Ngoài ra, người ta biết rằng một chiếc cốc nặng 100 gram và một chiếc xe tải rỗng - 3 tấn.
Đầu ra
In một số duy nhất - số cốc tối đa có thể mang trên chuyến bay đầu tiên, thời gian không quá 24 giờ.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
3 3
1 2 10 3000220
2 3 20 3000201
1 3 1 3000099
|
2 |