În ţara lui Scania camioanele primesc benzină pe şosele în loc să consume. O şosea de x km îi umple lui Red rezervorul cu x litri de benzină. Red porneşte din oraşul A şi vrea să ajungă în oraşul B cu camionul. Deoarece Neck cel grăbit vrea să ia toată benzina din rezervorul camionului lui Red în canistre de K litri, rezervorul trebuie să conţină un număr de litri divizibil cu K. Oraşele sunt numerotate de la 1 la N, iar între acestea există M şosele bidirecţionale. Oraşele A şi B sunt printre cele N oraşe.
Cerinţă
Găsiţi drumul de lungime minimă dintre oraşele A şi B cu proprietatea că rezervorul este gol la plecare (din A) şi va conţine la sosire (oraşul B) un număr de litri divizibil cu K.
Date de intrare
Fişierul de intrare benzina2.in conţine pe prima linie numerele naturale NKAB cu semnificaţia din enunţ. Pe următoarea linie este numărul M. Pe următoarele M linii se află câte trei numere naturale xyk cu semnificaţia că între oraşele x şi y este o şosea de k kilometri.
Date de ieşire
Fişierul de ieşire benzina2.out va conţine pe prima linie distanţa minimă a unui drum cu proprietatea cerută. Pe a doua linie se găseşte un drum cu proprietatea cerută, care este minim lexicografic, dacă sunt citite orașele de pe respectivul drum pornind de la B spre A. Drumul este specificat prin succesiunea nodurilor care îl formează de la A la B, separate prin spații.
Restricţii
Întotdeauna există soluţie pentru datele de test. 1 ≤ A, B ≤ N ≤ 5000 1 ≤ M ≤ 10000 1 ≤ k ≤ 300 1 ≤ K ≤ 50