Problem
Untuk Sekolah Komputer Musim Panas yang seterusnya, telah diputuskan untuk menyediakan kalangan untuk pelajar sekolah dan semua guru.
Mempunyai tabiat melakukan perkara penting pada saat terakhir, pereka bentuk menyelesaikan reka letak dua hari sebelum sekolah bermula. Ia akan mengambil satu hari lagi untuk pengeluar membuat cawan dan meletakkan imej padanya. Hanya mengambil masa 24 jam untuk NATO membawa mug dari kilang ke LKSH.
Tempahan untuk 10,000,000 mug (iaitu, jumlah tempahan penganjur), sudah tentu, tidak boleh dibawa pergi dalam satu penerbangan. Namun, untuk penerbangan pertama saya ingin membawa jumlah maksimum mug. Satu lori berat ditempah untuk pengangkutan. Tetapi ada satu kaveat: di beberapa jalan ada had pada berat kereta. Oleh itu, jika kereta sarat dengan mug hingga ke bola mata, maka ia mungkin tidak boleh menggunakan laluan terpendek, tetapi anda perlu mengambil lencongan. Malah mungkin berlaku kerana ini, trak tidak akan mempunyai masa untuk sampai ke kem tepat pada masanya, dan ini tidak boleh dibenarkan. Jadi, berapa banyak mug boleh dimuatkan ke dalam kereta untuk mempunyai masa untuk membawa kargo berharga ini tepat pada masanya, dan tanpa melanggar peraturan jalan raya?
Input
Baris pertama mengandungi nombor n (1≤n≤500) dan m - bilangan nod dalam peta jalan dan bilangan jalan, masing-masing. Baris m seterusnya mengandungi maklumat tentang jalan raya. Setiap jalan diterangkan pada baris yang berasingan seperti berikut. Mula-mula, nombor titik simpang yang disambungkan dengan jalan ini diberi, kemudian masa yang diperlukan untuk menempuh jalan ini, dan akhirnya, berat maksimum kereta yang dibenarkan memandu di jalan ini. Adalah diketahui bahawa semua jalan menghubungkan titik yang berbeza, dan untuk setiap pasangan mata terdapat paling banyak satu jalan yang menghubungkannya secara langsung. Semua nombor dipisahkan oleh satu atau lebih ruang.
Titik nodal dinomborkan dari 1 hingga n. Pada masa yang sama, kilang untuk pengeluaran mug mempunyai nombor 1, dan LKSH - nombor n. Masa perjalanan di jalan raya diberikan dalam minit dan tidak melebihi 1440 (24 jam). Had jisim diberikan dalam gram dan tidak melebihi satu bilion. Di samping itu, diketahui bahawa satu cawan seberat 100 gram, dan sebuah trak kosong - 3 tan.
Output
Cetak satu nombor - bilangan maksimum cawan yang boleh dibawa pada penerbangan pertama, menghabiskan tidak lebih daripada 24 jam.
Contoh
| # |
Input |
Output |
| 1 |
3 3
1 2 10 3000220
2 3 20 3000201
1 3 1 3000099
|
2 |