roadtrip

Valorosul României a scăpat deja de stresul sesiunii și se gândește acum la o vacanță binemeritată. El și-a propus să plece într-un roadtrip din orașul $A$ în orașul $B$. Pentru aceasta și-a procurat o hartă pe care sunt marcate $N$ orașe, numerotate de la $1$ la $N$, conectate prin $M$ autostrăzi bidirecționale de lungimi date și a scos R-mobilul din garaj. R-mobilul este o mașină pe benzină cu rezervor de capacitate $C$ litri potrivită pentru un roadtrip. În fiecare oraș de pe hartă există o singură benzinărie unde Valorosul României poate alimenta. Din motive necunoscute, în aceste benzinării trebuie obligatoriu efectuat plinul rezervorului, așa că R-mobilul va pleca din fiecare benzinărie din care a alimentat cu rezervorul plin cu $C$ litri de benzină. Pentru fiecare benzinărie se cunoaște timpul $t$ necesar alimentării, dat în minute, și acesta nu depinde de cantitatea de benzină cumpărată. Parcurgerea unei autostrăzi de lungime $d$ durează $d$ minute și consumă $d$ litri de benzină. Pe autostrăzi nu există benzinării, așa că Valorosul României trebuie să fie atent când pleacă dintr-un oraș să aibă suficientă benzină pentru a putea ajunge la orașul destinație.

Valorosul României vrea să ajungă cât mai repede din orașul $A$ în orașul $B$. Fiindcă este plin de bani, obținuți din bursele primite de la Ministerul Educației Naționale, nu îi pasă câtă benzină consumă în acest roadtrip.

Cerință

Determinați timpul minim în care Valorosul României poate ajunge din orașul $A$ în orașul $B$.

Date de intrare

Fișierul de intrare roadtrip.in conține pe prima linie două numere naturale $N$ și $M$, cu semnificația din enunț. Pe a doua linie din fișier sunt $N$ numere naturale care reprezintă timpul $t$ de realizare a plinului rezervorului R-mobilului pentru fiecare oraș, pe următoarele $M$ linii se găsesc 3 numere naturale $x$, $y$ și $d$ care reprezintă o autostradă de lungime $d$ între orașul $x$ și orașul $y$, iar pe ultima linie a fișierului se află 3 numere naturale $A$, $B$, și $C$ cu semnificația din enunț.

Date de ieșire

În fișierul de ieșire roadtrip.out se va scrie un singur număr natural, care reprezintă timpul minim în care Valorosul României ajunge din orașul $A$ în orașul $B$ sau $-1$ dacă acest lucru nu este posibil.

Restricții și precizări

• $1 \leq N, C \leq 500; 1 \leq M \leq 1000$;
• $1 \leq x, y, A, B \leq N$;
• $d \leq C$, pentru orice triplet $(x, y, d)$; $t \leq C$;
• Pentru $10\%$ din teste, timpul $t$ de efectuare a plinului de benzină este $0$ pentru toate orașele și lungimea $d$ a tuturor autostrăzilor este $1$;
• Pentru $30\%$ din teste, timpul de efectuare a plinului de benzină este $0$ pentru toate orașele;
• Pentru alte $20\%$ din teste, $M = N-1$ iar toate cele $M$ muchii sunt de forma $(x, x+1)$, $x = \overline{1..N-1}$.

Exemplul 1

roadtrip.in

4 4 
0 16 8 0 
1 2 5 
1 3 7 
2 4 11 
3 4 15 
1 4 16

roadtrip.out

16

Exemplul 2

roadtrip.in

4 4 
0 16 8 0 
1 2 5 
1 3 7 
2 4 11 
3 4 15 
1 4 15

roadtrip.out

30

Explicații

Imaginea de mai jos este valabilă pentru ambele exemple.

În primul exemplu, R-mobilul are suficientă benzină ca să ajungă din orașul $1$ în orașul $4$, fără să realimenteze. Timpul minim este dat prin adunarea timpilor de pe autostrada $(1,2)$ și autostrada $(2,4)$: $5 + 11 = 16$.

În al doilea exemplu, R-mobilul trebuie să realimenteze pentru a putea ajunge din orașul $1$ în orașul $4$. Preferă să facă realimentarea în orașul $3$, deoarece timpul total este minim: $7 + 8 + 15 = 30$. Dacă ar fi realimentat în orașul $2$, timpul total ar fi fost $5 + 16 + 11 = 32$.