Ziņnesis ezis ir tālu no savas alas, bet, pirms viņš tur dotas, ir jaapmeklē vēl dažas malas. Viņam jānogādā bļodas un rotas; kā arī jaapciemo ciema meitas, garlaicību kveldēt. Ezim jānogādā visas ziņas, ja negrib ar zivīm peldēt.

Pirmajā rindā dots ciemu skaits n (3 <= n <= 100), m (1 <= m <= 10) un k (2 <= k <= 4950)

Otrajā rindā seko m skaitļi - ciemu numuri, kuros jānogādā ziņas. 

Trešajā rindā doti sākuma un beigu ciema numurs.

Tālāk seko k rindas, katra saturot vērtības a, b  un d (1 <= a,b,d <= 100) - ciems a un b atrodas attālumā d

Jaizvada mazākā iespējamā distance, lai no sākuma nokļūtu uz beigām, nogādājot visas ziņas.