Prisonbreak

Pia și Mițuca au ajuns la închisoare după ce au furat 10 conserve cu ton și au ucis 7 muște cu premeditare. Acum, închise departe de cele mai pufoase și călduroase loculețe de dormit, au decis să evadeze.

Închisoarea este sub forma unui graf neorientat cu $N$ noduri și $M$ muchii. Pia și Mițuca se află în nodul $1$, iar scopul lor este să ajungă în nodul $N$ pentru a evada. Fiecare nod are o culoare reprezentată printr-un număr natural, exceptând nodurile $1$ și $N$, care sunt necolorate.

Fiecare muchie a grafului are un cost de bobițe pe care protagonistele trebuie să îl plătească pentru a parcurge muchia respectivă.

Din păcate, nodurile sunt camere securizate digital pentru a preveni evadarea criminalilor periculoși. Singura metodă de a intra într-o astfel de cameră fără să sune alarma este prin dezactivarea senzorilor de protecție. Pentru aceasta, este nevoie de o cheie magnetică care să aibă aceeași culoare cu cea a camerei în care se intră. Din fericire, Pia și Mițuca se află în camera $1$, unde se găsesc chei magnetice de toate culorile posibile. Totuși, acestea fiind foarte greu de cărat, fiecare pisicuță poate să pornească la drum cu maxim o astfel de cheie. Prin urmare, fiind o echipă, pisicile pot porni la drum cu maxim $2$ culori distincte, pe care o să le numim culorile $A$ și $B$. Având aceste $2$ chei cu culorile $A$ și $B$, pisicuțele pot parcurge doar noduri care au culoarea $A$ sau culoarea $B$ (nodurile unde pot dezactiva senzorii de protecție).

În plus, acestea au primit un mesaj telepatic de la Tomiță, un motănel periculos. Tomiță le-a spus că a analizat închisoarea și a realizat că nu există o componentă conexă de noduri de aceeași culoare care să fie mai mare de $50$ de noduri.

Cerință

Deoarece Pia și Mițuca vor să rămână cu cât mai multe bobițe la final, aflați costul minim de bobițe pe care trebuie să îl plătească pentru a ajunge din nodul $1$ în nodul $N$ știind că pot parcurge maxim $2$ culori diferite. Se cere, de asemenea, numărul de drumuri de cost minim între nodul $1$ și nodul $N$ în condițiile date, modulo $666 \ 013$, și un exemplu de astfel de drum de cost minim.

Date de intrare

Fișierul de intrare prisonbreak.in conține pe prima linie două numere naturale $N$ și $M$, reprezentând numărul de noduri din graf, respectiv numărul de muchii din graf. Următoarea linie conține $N - 2$ valori reprezentând culorile nodurilor numerotate de la $2$ la $N - 1$. Începând cu linia $3$, pe următoarele $M$ linii se află câte $3$ numere naturale $A, B, C$ reprezentând faptul că există o muchie neorientată între nodul $A$ și nodul $B$, iar costul de parcurgere a muchiei este $C$.

Date de ieșire

Fișierul de ieșire prisonbreak.out trebuie să conțină pe prima linie costul minim de a ajunge din nodul $1$ în nodul $N$ în condițiile menționate în enunț. Pe a doua linie va conține numărul de drumuri distincte, $K$, cu acest cost, care respectă condițiile din enunț, modulo $666 \ 013$}. Urmează două linii ce reprezintă un exemplu de drum parcurs dintre aceste $K$. Dacă există mai multe, se poate afișa oricare. Linia a $3$-a din fișier va conține un număr natural $P$ reprezentând numărul de noduri parcurse în drumul ales. Pe linia a $4$-a se vor afișa $P$ numere naturale reprezentând nodurile parcurse de cele $2$ pisicuțe pe drumul ales.

Restricții și precizări

• $4 \leq N \leq 50 \ 000$;
• $4 \leq M \leq 200 \ 000$;
• $1 \leq$ culorile nodurilor $\leq N$;
• $1 \leq$ costurile muchiilor $\leq 1 \ 000 \ 000 \ 000$;
• Se garantează că între oricare două noduri distincte există cel mult o muchie;
• Se garantează că există cel puțin un drum de la nodul $1$ la nodul $N$ folosind cel mult două culori.
• $40\%$ din punctaj se va acorda pentru determinarea costului minim al drumului;
• $40\%$ din punctaj se va acorda pentru determinarea numărului de drumuri de cost minim;
• $20\%$ din punctaj se va acorda pentru reconstituirea unui drum de cost minim.

Exemplul

prisonbreak.in

7 8
1 2 3 2 1
1 2 10
1 3 7
2 4 5
3 4 8
4 5 3
5 7 5
4 6 4
6 7 2

prisonbreak.out

21
1
5
1 2 4 6 7

Explicație

Avem $7$ noduri, dintre care nodurile $1$ și $7$ sunt necolorate, iar celelalte norduri sunt colorate astfel:

• Nodul $2$ are culoarea $1$;
• Nodul $3$ are culoarea $2$;
• Nodul $4$ are culoarea $3$;
• Nodul $5$ are culoarea $2$;
• Nodul $6$ are culoarea $1$.

Drumul de cost minim de la nodul $1$ la nodul $7$ este obținut prin folosirea culorilor $1$ și $3$, trecând în ordine prin nodurile $1, 2, 4, 6, 7$ și având costul total $10 + 5 + 4 + 2 = 21$. Un alt drum, folosind culorile $2$ și $3$, trece prin nodurile $1, 3, 4, 5, 7$ și are costul $7 + 8 + 3 + 5 = 23$, care nu este minim. Deci, numărul de drumuri de cost minim este 1.