Problem
Önümüzdeki Yaz Bilgisayar Okulu için hem okul çocukları hem de tüm öğretmenler için çemberler hazırlanmasına karar verildi.
Önemli işleri son anda yapma alışkanlığı olan tasarımcı, okul başlamadan iki gün önce yerleşimi bitirdi. Üreticinin kupa yapıp üzerlerine resim koyması bir gün daha alacak. NATO'nun kupaları fabrikadan LKSH'ye götürmesi yalnızca 24 saat sürüyor.
10.000.000 kupalık bir sipariş (yani, organizatörlerin sipariş ettiği miktar) elbette bir uçuşta alınamaz. Ancak ilk uçuş için maksimum sayıda kupa getirmek istiyorum. Taşıma için bir ağır kamyon sipariş edildi. Ancak bir uyarı var: bazı yollarda arabanın ağırlığı için bir sınır var. Bu nedenle, araba gözbebeklerine kadar kupalarla doluysa, o zaman en kısa rotayı kullanmak mümkün olmayabilir, ancak yoldan sapmanız gerekecektir. Hatta bu nedenle kamyonun kampa zamanında yetişmesi için zaman kalmayabilir ve buna izin verilemez. Peki, bu değerli kargoyu zamanında ve yol kurallarını ihlal etmeden getirmek için zamana sahip olmak için arabaya kaç kupa yüklenebilir?
Giriş
İlk satır, sırasıyla n (1≤n≤500) ve m - yol haritasındaki düğümlerin sayısı ve yolların sayısını içerir. Sonraki m satırlar yollar hakkında bilgi içerir. Her yol aşağıdaki gibi ayrı bir satırda açıklanmıştır. Önce bu yolun birbirine bağlandığı kavşak noktalarının sayısı, ardından bu yolu kat etmesi için geçen süre ve son olarak da bu yolda gitmesine izin verilen bir arabanın maksimum ağırlığı verilir. Tüm yolların farklı noktaları birbirine bağladığı ve her nokta çifti için onları doğrudan bağlayan en fazla bir yol olduğu bilinmektedir. Tüm sayılar bir veya daha fazla boşlukla ayrılır.
Düğüm noktaları 1'den n'ye kadar numaralandırılmıştır. Aynı zamanda, kupa üretim tesisi 1 numaraya ve LKSH - n numaraya sahiptir. Karayolu üzerinde seyahat süresi dakika cinsinden verilir ve 1440'ı (24 saati) geçmez. Kütle sınırı gram cinsinden verilir ve bir milyarı geçmez. Ayrıca bir kupanın 100 gram, boş bir kamyonun - 3 ton.
Çıktı
Tek bir sayı yazdırın - en fazla 24 saat harcayarak ilk uçuşta getirilebilecek maksimum kupa sayısı.
Örnekler
| # |
Girdi |
Çıktı |
| 1 |
3 3
1 2 10 3000220
2 3 20 3000201
1 3 1 3000099
|
2 |