Problem
Per la prossima Summer Computer School, si è deciso di preparare dei circoli sia per gli scolari che per tutti gli insegnanti.
Avendo l'abitudine di fare le cose importanti all'ultimo momento, il designer ha terminato il layout due giorni prima dell'inizio della scuola. Ci vorrà un altro giorno prima che il produttore realizzi tazze e vi metta un'immagine. La NATO impiega solo 24 ore per portare le tazze dalla fabbrica a LKSH.
Un ordine di 10.000.000 di tazze (vale a dire quante ne hanno ordinate gli organizzatori), ovviamente, non può essere portato via in un solo volo. Tuttavia, per il primo volo voglio portare il numero massimo di tazze. Un camion pesante è stato ordinato per il trasporto. Ma c'è un avvertimento: su alcune strade c'è un limite al peso dell'auto. Pertanto, se l'auto è carica di tazze ai bulbi oculari, potrebbe non essere possibile utilizzare il percorso più breve, ma dovrai fare una deviazione. Può anche succedere che a causa di ciò il camion non abbia il tempo di raggiungere il campo in tempo, e questo non può essere permesso. Quindi, quante tazze possono essere caricate in macchina per avere il tempo di portare questo prezioso carico in tempo e senza violare le regole della strada?
Input
La prima riga contiene i numeri n (1≤n≤500) e m - rispettivamente il numero di nodi nella mappa stradale e il numero di strade. Le successive m righe contengono informazioni sulle strade. Ogni strada è descritta su una riga separata come segue. Per prima cosa vengono indicati i numeri dei punti di giunzione collegati da questa strada, quindi il tempo necessario per percorrere questa strada e infine il peso massimo di un'auto che può circolare su questa strada. È noto che tutte le strade collegano punti diversi e per ogni coppia di punti esiste al massimo una strada che li collega direttamente. Tutti i numeri sono separati da uno o più spazi.
I punti nodali sono numerati da 1 a n. Allo stesso tempo, l'impianto per la produzione di tazze ha il numero 1 e LKSH - il numero n. Il tempo di percorrenza su strada è espresso in minuti e non supera 1440 (24 ore). Il limite di massa è espresso in grammi e non supera il miliardo. Inoltre, è noto che una tazza pesa 100 grammi e un camion vuoto - 3 tonnellate.
Uscita
Stampa un numero unico - il numero massimo di tazze che possono essere portate sul primo volo, spendendo non più di 24 ore.
Esempi
| # |
Input |
Uscita |
| 1 |
3 3
1 2 10 3000220
2 3 20 3000201
1 3 1 3000099
|
2 |