Deşi supăraţi pentru că anul trecut nu au reuşit să se plimbe pe planeta recent descoperită Kubus, Alf şi Zilla nu se dau bătuţi. Cei doi au cerut ajutor de la vrăjitorul galez Fflamddwyn care i-a învăţat pe aceştia o nouă metodă de deplasare: teleportarea.
Fflamddwyn a împărţit fiecare dintre cele 6 feţe ale planetei Kubus (pentru cine nu ştie, planeta Kubus este sub formă de cub, după cum sugerează şi numele) în NxN celule egale, câte N celule pe fiecare dintre cele N rânduri. Prin câteva vrăji, acesta a amplasat portaluri în câteva dintre aceste celule. Fflamddwyn a legat aceste portaluri între ele prin M conexiuni cu fix două capete (portalul de intrare şi portalul de ieşire). Vrăjitorul galez menţionează că pentru utilizarea fiecărei conexiuni, trebuie plătită o sumă de bani (exprimată în Koroane).
Pentru a-i antrena în utilizarea portalurilor, Fflamddwyn îl trimite pe Alf în celula de pe faţa FA, linia LA, coloana CA, şi pe Zilla în celula de pe faţa FZ, linia LZ, coloana CZ. Acesta le garantează celor doi că în poziţiile lor iniţiale există cel puţin un portal. Fflamddwyn le cere celor doi să utilizeze o succesiune de portaluri până într-o celulă unde să se întâlnească. Desigur, există şi cazul în care cei doi nu se pot întâlni. Pentru a fi siguri că nu vor folosi portalurile inutil, vrăjitorul galez le pune condiţia ca suma de bani cheltuită de cei doi să fie minimă. În plus, fiecare dintre cei doi trebuie să folosească cel puţin un portal.

Cerinţă

Pentru a fi sigur că Fflamddwyn le dă verdictul corect (dacă au mers optim sau nu) lui Alf şi Zilla la finalul antrenamentului, calculaţi costul total minim precum şi costurile pentru fiecare dintre cei doi prieteni.

Date de intrare

Fişierul de intrare kubus2.in conţine pe prima linie N, dimensiunea planetei Kubus.
A doua linie conţine numerele FA LA CA FZ LZ CZ cu semnificaţia din enunţ.
Următoarea linie conţine M, numărul de legături de portaluri.
Pe următoarele M linii se vor afla câte 6 numere, PFi PLi PCi QFi QLi QCi K reprezentând legătura dintre un portal aflat în celula cu coordonatele PFi, PLi, PCi şi un portal aflat în celula cu coordonatele QFi, QLi, QCi, care necesită o sumă de bani K pentru fiecare folosire de către oricare dintre cei doi prieteni.

Date de ieşire

Fişierul de ieşire kubus2.out conţine pe prima linie, în cazul în care există soluţie, numărul natural S, suma totală cheltuită de Alf şi Zilla, iar pe linia a doua 2 numere naturale, SA şi SZ, separate prin câte un spaţiu, semnificând suma de bani cheltuită de Alf, respectiv suma de bani cheltuită de Zilla. Dacă nu există soluţie, prima linie va conţine valoarea -1.

Restricţii

• 2 ≤ N ≤ 1000
• 1 ≤ FA, FZ, PF , QF ≤ 6
• 2 ≤ M ≤ 1500
• 1 ≤ LA, CA, LZ, CZ, PL, PC, QL, QC ≤ N
• 1 ≤ K ≤ 100
• Toate legăturile sunt bidirecţionale
• Poziţiile iniţiale ale celor doi sunt diferite
• Pot exista mai multe portaluri în aceeaşi celulă
• Pot exista mai multe conexiuni între aceleaşi două celule
• Alf şi Zilla au voie să se deplaseze doar prin portaluri!
• Alf şi Zilla aleg pentru fiecare celulă de pe traseul fiecăruia dacă rămân în celula respectivă sau folosesc una dintre legături care au portal în celula actuală.
• Dacă există mai multe posibilităţi de a obţine suma totală minimă, se va alege cea care are suma cheltuită de Alf cea mai mică.

Exemple

kubus2.in	kubus2.out	Explicaţii
5 1 2 3 3 1 2 4 1 2 3 2 4 5 2 1 2 3 2 1 2 5 2 4 5 3 1 2 3 2 1 2 3 1 2 7	5 2 3	Alf merge din celula (1,2,3) în celula (2,4,5) şi cheltuie 2 Koroane. Zilla merge din celula (3,1,2) în celula (2,4,5) şi cheltuie 3 Koroane. Total: 2 + 3 = 5 Koroane.
3 4 1 2 3 2 2 3 4 1 2 1 2 6 5 2 3 4 4 1 2 3 3 2 2 1 1 1 2	-1	Nu există nicio succesiune de conexiuni care să facă legătura dintre poziţia iniţială a lui Alf şi poziţia iniţială a lui Zilla.

autor: Alexandru Cohal

propunător: Prof. Emanuela Cerchez

Colegiul Naţional ″Emil Racoviţă″

emanuela.cerchez@gmail.com