Транспорт на вакцини
Во една сиромашна земја на северот конечно пристигнале вакцини, кои сега треба да се транспортираат најбрзо што може од главниот град до другите градови. Друг проблем е што вакцините мора да бидат на многу ниска температура, а таква апаратура во земјата не постои, па одлучиле да ги превезуваат вакцините само по патиштата на кои има снег во моментов. Трет проблем е што благајникот во Министерството за здравство го знае најкраткото растојание до секој град и е спремен да покрие трошоци само за толкаво растојание и ништо повеќе.
Нека вам ви е даден опис на патната мрежа меѓу градовите на следниот начин: има N градови означени од 1 до N, и има M директни двонасочни патишта кои ги поврзуваат градовите. Главниот град е означен со 1. Секој директен пат меѓу два града е опишан со броевите A, B, C и D, каде што А и B се градовите, C ја означува должината на патот, додека D е 0 доколку нема снег на патот или 1 доколку има снег на патот во моментов. Помеѓу два града A и B може да постојат повеќе директни патишта, а сигурни сме и дека постои пат од главниот град до секој друг град.
Ваша задача е да утврдите која е должината на најкраткиот пат од главниот град до градот N и дали постои пат од 1 до N со најдената должина кој се состои само од директни патишта на кои има снег во моментов.
Влез
Во првиот ред се наоѓаат броевите N (1 ≤ N ≤ 1000) и M (N-1 ≤ M ≤ 3000).
Во следните M редови се наоѓаат по четири броја A, B, C и D, кои се однесуваат на патиштата и се опишани погоре (1 ≤ A, B ≤ N, 1 ≤ C ≤ 1000, 0 ≤ D ≤ 1).
Излез
Во првиот ред запишете ја должината на најкраткиот пат до градот N.
Во вториот ред запишете “DA” доколку постои пат од 1 до N со најдената должина кој се состои само од директни патишта на кои има снег во моментов. Во спротивно запишете “NE”.
Ограничувања
Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes
Примери
влез 6 7 1 2 1 1 2 3 1 1 3 6 1 0 1 4 1 1 4 6 1 1 1 5 1 1 5 6 1 0 | излез 2 DA |
влез 6 7 1 2 1 1 2 3 1 1 3 6 1 1 1 4 1 0 4 6 1 1 1 5 1 1 5 6 1 0 | излез 2 NE |
Објаснување за првиот пример:
Најкраткиот пат од градот 1 до градот 6 има должина 2. Патеката 1 -> 4 -> 6 е една патека со должина 2 на која снегот не е стопен, па затоа одговорот е DA.
Објаснување за вториот пример:
Најкраткиот пат од градот 1 до градот 6 е повторно со должина 2. Но сега, сите патеки со должина 2 од градот 1 до градот 6 минуваат низ патишта со стопен снег. Па затоа, одговорот е NE. Да забележиме дека постои патека 1 -> 2 -> 3 -> 6 на која целиот снег стои, но оваа има подолга должина од бараната.