Problem
次回のサマー コンピューター スクールでは、学童とすべての教師のためにサークルを用意することが決定されました。
最後の瞬間に重要なことをする習慣があるため、デザイナーは学校が始まる 2 日前にレイアウトを完成させました。メーカーがマグカップを作って画像を載せるには、もう1日かかります。 NATO がマグカップを工場から LKSH に運ぶのに 24 時間しかかかりません。
もちろん、10,000,000 個のマグカップ (つまり、主催者が注文した数) の注文は、1 回のフライトで取り除かれることはありません。ただ、初飛行はマグカップを最大限持っていきたいです。輸送用に1台の大型トラックが注文されました。ただし、注意点が 1 つあります。一部の道路では、車の重量に制限があります。そのため、眼球にマグカップを積んでいる場合は、最短ルートを利用できない場合があり、迂回する必要があります。このため、トラックが時間通りにキャンプに到着する時間がないこともあり、これは許可されません。では、交通規則に違反することなく、この貴重な貨物を時間通りに運ぶために、何個のマグカップを車に積み込むことができるでしょうか?
入力
最初の行には、数値 n (1≤n≤500) と m が含まれています。それぞれ、道路地図のノード数と道路数です。次の m 行には、道路に関する情報が含まれています。各道路は、次のように別の行に記載されています。最初に、この道路で接続されている分岐点の数、次にこの道路を移動するのにかかる時間、最後にこの道路を走行できる自動車の最大重量が与えられます。すべての道路が異なるポイントを接続し、ポイントの各ペアに対して、それらを直接接続する道路が最大で 1 つ存在することが知られています。すべての数字は 1 つ以上のスペースで区切られています。
節点には 1 から n までの番号が付けられます。同時に、マグカップの生産工場は1番、LKSH - 番号nです。道路での移動時間は分単位で与えられ、1440 (24 時間) を超えません。質量制限はグラム単位で与えられ、10 億を超えません。さらに、1 つのマグカップの重さは 100 グラムであり、空のトラックは - 3トン。
出力
数字を 1 つ記入してください。最初のフライトで 24 時間以内に持ち込めるマグカップの最大数です。
例
<頭>
| # |
入力 |
出力 |
<本体>
| 1 |
3 3
1 2 10 3000220
2 3 20 3000201
1 3 1 3000099
|
2 |