Un agent secret are o hartă pe care sunt marcate N obiective militare. El se află, iniţial, lângă obiectivul numerotat cu 1 (baza militară proprie) şi trebuie să ajungă la obiectivul numerotat cu N (baza militară inamică). În acest scop, el va folosi drumurile existente, fiecare drum legând 2 obiective distincte. Fiind o misiune secretă, deplasarea agentului va avea loc noaptea; de aceea, el are nevoie de o lanternă. Pentru aceasta, el are de ales intre K tipuri de lanterne – o lanternă de tipul W (1 <= W <= K) are baterii care permit consumul a W waţi, după consumul acestor waţi, lanterna nu mai luminează. Din fericire, unele dintre obiective sunt baze militare prietene, astfel că, o dată ajuns acolo, el îşi poate reîncărca bateriile complet. Agentul trebuie sa aibă grijă ca, înainte de a merge pe un drum între două obiective, cantitatea de waţi pe care o mai poate consuma să fie mai mare sau egală cu cantitatea de waţi pe care o va consuma pe drumul respectiv.
Cerinţă
Cunoscând drumurile dintre obiective şi, pentru fiecare drum, durata necesară parcurgerii drumului şi numărul de waţi consumaţi de lanternă, determinaţi tipul de lanternă cu numărul cel mai mic, astfel încât durata deplasării sa fie minimă (dintre toate tipurile de lanternă cu care se poate ajunge în timp minim la destinaţie, interesează lanterna cu consumul cel mai mic).
Date de intrare
Pe prima linie a fişierului lanterna.in se află numerele întregi N şi K, separate printr-un spaţiu. Pe următoarea linie se află N numere întregi din mulţimea {0,1}. Daca al i-lea număr este 1, aceasta înseamnă că obiectivul cu numărul i este o bază militară prietenă (adică agentul îşi poate reîncărca bateriile lanternei daca ajunge la acest obiectiv); dacă numărul este 0, agentul nu îşi va putea reîncărca bateriile. Primul număr din linie este 1, iar ultimul este 0. Pe cea de-a treia linie a fişierului se află numărul M de drumuri dintre obiective. Fiecare din următoarele M linii conţine câte 4 numere întregi separate prin spaţii: a b T W, având semnificaţia că există un drum bidirecţional între obiectivele a şi b (a<>b), care poate fi parcurs într-un timp T şi cu un consum de W waţi.
Date de ieşire
In fişierul lanterna.out se vor afişa două numere întregi, separate printr-un spaţiu : Tmin şi Wmin. Tmin reprezentând durata minimă posibilă a deplasării de la obiectivul 1 la obiectivul N, iar Wmin reprezintă tipul de lanternă cu numărul cel mai mic pentru care se obţine acest timp.
Restricţii
2 <= N <= 50
1 <= K <= 1000
1 <= M <= N*(N-1)/2
Între două oraşe diferite poate exista maximum un drum direct.
Pentru fiecare drum, durata parcurgerii este un număr întreg intre 1 şi 100, iar numărul de waţi consumaţi este un număr întreg între 0 şi 1000
Se garantează că există cel puţin un tip de lanternă pentru care deplasarea să fie posibilă.