Ջերմաստիճաններ
Ունենք շինություն, որտեղ կա
N սենյակ, որոնք համարակալված են 1ից N թվերով։ Այդ սենյակներից որոշները միացված են երկկողմանի միջանցքներով, որոնց ընդհանուր քանակը M է։ Բայց մեր շինությունը շատ յուրահատուկ է, և հնարավոր է, որ լինեն նույն երկու սենյակը միացնող 1ից ավելի միջանցքներ։ Ավելին, հնարավոր է լինի միջանցք, որը միացնում է սենյակը ինքն իրեն։ Բոլոր միջանցքներն ունեն 1 միավոր երկարություն։Մեր ռոբոտը պետք է շինության A սենյակից գնա B սենյակ՝ հաջորդաբար շարժվելով այդ միջանցքներով։Սակայն ամեն ինչ այդքան պարզ չէ։ iրդ միջանցքի ջերմաստիճանը ti է (1 ≤ i ≤ M), իսկ ռոբոտը շատ զգայուն է ջերմաստիճանի փոփոխության նկատմամբ։ Այսպիսով, ռոբոտի ճանապարհի հաջորդական միջանցքների ջերմաստիճանների տարբերությունը բացարձակ արժեքով չպետք է գերազանցի D թիվը։ Եթե ճանապարհի ընթացքում ռոբոտը պետք է հաջորդաբար անցնի (i=1,2,…,k-1) պայմաններին: Սենյակների ջերմաստիճաններն անտեսվում են։ Պետք է գտնել նշված պայմաններին բավարարող ամենակարճ ճանապարհի երկարությունը տրված A և B թվերի համար։Մուտքային տվյալներ
Առաջին տողում տրված են
3 ամբողջ թվեր՝ N, M, D։- Թեստերի առաջին խմբի համար
։
- Թեստերի երկրորդ խմբի համար
։
Հաջորդ
M տողերում տրված են միջանցքների նկարագրությունները։ Ամեն տող պարունակում է 3 ամբողջ թիվ՝ ui, vi, ti: Սա նշանակում է, որ iրդ միջանցքը միացնում է Q (1 ≤ Q ≤ 10) թիվը՝ հարցումների քանակը։Հաջորդ Q տողերում տրված են Ելքային տվյալներ
Պետք է արտածել
Q հատ թիվ՝ տրված -1։Օրինակ
Մուտք. | Ելք. |
6 9 5
6 6 -42
2 1 4
2 3 6
3 2 7
5 2 11
6 1 12
3 1 15
3 4 16
6 5 18
2
1 5
2 4 | 4
-1 |
Աղբյուրը՝ Հանրապետական 2021
Constraints
Time limit: 7 seconds
Memory limit: 512 MB
Output limit: 1 MB