Laiko ribojimas: 1s

Atminties ribojimas: 1024MB

Duomenų failas: keliu_uzbaigimas.in

Rezultatų failas: keliu_uzbaigimas.out

Jei norite pateikti savo sprendimą - prisijunkite.

2. Domantas ir keliai

Domantas nupiešė grafą su n viršūnių sunumeruotų nuo 0 iki n-1 bei m neorientuotų briaunų. Kiekviena grafo briauna turi teigiamą svorį.

Sekančią dieną Domantas suprato, jog kažkas ištrynė kai kuriuos briaunų svorius. Taigi jis nutarė užrašyti naujus svorius vietoje nutrintų. Domantas nori sužinoti, ar jis galės prirašyti trūkstamus svorius taip, kad mažiausio svorio kelias tarp viršūnių s ir t būtų lygiai L.

Jūsų užduotis - išspausdinti "YES" jei Domanto užduotis yra įmanoma, kitu atveju išspausdinti "NO".

Pradiniai duomenys

Pirmoje eilutėje pateikti penki sveikieji skaičiai n, m, L, s bei t (2\\leqn\\leq1000,1\\leqm\\leq10000,1\\leqL\\leq10^9,0\\leqs,t\\leqn-1,s\\neqt). Sekančiose m eilučių pateikti duomenys apibūdinantys grafo briaunas. i-tojoje eilutėje pateikti trys sveikieji skaičiai u_i,v_i,w_i (0\\lequ_i,v_i\\leqn-1,u_i\\neqv_i,0\\leqw_i\\leq10^9) reiškiantys, jog viršūnes u_i,v_i jungia briauna su svoriu w_i. Jei w_i=0, tai reiškia, jog šios briaunos svoris buvo nutrintas.

Rezultatai

Išspausdinkite "YES" jei Domanto užduotis yra įmanoma, kitu atveju išspausdinkite "NO".

Pavyzdžiai

Pradiniai duomenys Rezultatai 
5 5 13 0 4
0 1 5
2 1 2
3 2 3
1 4 0
4 3 4
 
YES
 
4 4 8 1 3
1 3 13
2 3 0
2 0 0
1 0 6
 
YES