Problem
Für die nächste Computerschule im Sommer wurde beschlossen, die Becher sowohl für die Schüler als auch für alle Lehrer vorzubereiten.
Mit der Angewohnheit, im letzten Moment wichtige Dinge zu erledigen, beendete der Designer zwei Tage vor Schulbeginn die Arbeit am Layout. Ein weiterer Tag wird vom Hersteller benötigt, um die Becher herzustellen und ein Bild darauf aufzutragen. Es bleiben nur 24 Stunden, um die Becher von der Fabrik zum LCSH zu bringen.
Eine Bestellung von 10000000 Exemplaren von Bechern (nämlich so viel haben die Organisatoren bestellt) kann natürlich nicht für einen Flug mitgenommen werden. Für den ersten Flug möchte ich jedoch die maximale Anzahl an Tassen mitbringen. Für den Transport wurde ein Schwerlastfahrzeug bestellt. Aber es gibt eine Einschränkung: Einige Straßen haben eine Beschränkung auf das Gewicht des Autos. Wenn Sie also das Auto mit Kreisen beladen, können Sie die kürzeste Route möglicherweise nicht nutzen, sondern müssen einen Umweg nehmen. Es kann sogar passieren, dass der LKW aus diesem Grund keine Zeit hat, das Lager rechtzeitig zu erreichen, und dies kann nicht erlaubt werden. Also, wie viele Becher können in ein Auto geladen werden, um diese wertvolle Fracht rechtzeitig zu bringen, ohne die Verkehrsregeln zu verletzen?
Eingabe
Die erste Zeile enthält die Zahlen n (1≤n≤500) und m ist die Anzahl der Knotenpunkte im Straßenverlauf und die Anzahl der Straßen. In den folgenden m-Zeilen finden Sie Informationen zu den Straßen. Jede Straße wird in einer separaten Zeile wie folgt beschrieben. Zuerst werden die Knotenpunktnummern angegeben, die diese Straße verbinden, dann die Zeit, die für die Fahrt auf dieser Straße aufgewendet wird, und schließlich das maximale Gewicht des Autos, das auf dieser Straße fahren darf. Es ist bekannt, dass alle Straßen verschiedene Punkte verbinden, wobei es für jedes Punktpaar nicht mehr als eine Straße gibt, die sie direkt verbindet. Alle Zahlen sind durch ein oder mehrere Leerzeichen getrennt.
Die Knotenpunkte sind mit Zahlen von 1 bis n nummeriert. Dabei hat die Becherfabrik die Nummer 1 und die LKS-Nummer n. Die Fahrzeit ist in Minuten angegeben und überschreitet 1440 (24 Stunden) nicht. Die Gewichtsgrenze ist in Gramm angegeben und überschreitet nicht eine Milliarde. Außerdem ist bekannt, dass ein Becher 100 Gramm wiegt und ein leerer LKW 3 Tonnen wiegt.
Ausgabe
Geben Sie eine Zahl aus - die maximale Anzahl an Tassen, die Sie für den ersten Flug mitbringen können, nachdem Sie maximal 24 Stunden ausgegeben haben.
Beispiele
| № |
Eingabe |
Ausgabe |
| 1 |
3 3
1 2 10 3000220
2 3 20 3000201
1 3 1 3000099
|
2 |