SPOJ in Armenian

Ունենք շինություն, որտեղ կա N սենյակ, որոնք համարակալված են 1ից N թվերով։ Այդ սենյակներից որոշները միացված են երկկողմանի միջանցքներով, որոնց ընդհանուր քանակը M է։ Բայց մեր շինությունը շատ յուրահատուկ է, և հնարավոր է, որ լինեն նույն երկու սենյակը միացնող 1ից ավելի միջանցքներ։ Ավելին, հնարավոր է լինի միջանցք, որը միացնում է սենյակը ինքն իրեն։ Բոլոր միջանցքներն ունեն 1 միավոր երկարություն։
Մեր ռոբոտը պետք է շինության A սենյակից գնա B սենյակ՝ հաջորդաբար շարժվելով այդ միջանցքներով։
Սակայն ամեն ինչ այդքան պարզ չէ։ iրդ միջանցքի ջերմաստիճանը ti է (1 ≤ i ≤ M), իսկ ռոբոտը շատ զգայուն է ջերմաստիճանի փոփոխության նկատմամբ։ Այսպիսով, ռոբոտի ճանապարհի հաջորդական միջանցքների ջերմաստիճանների տարբերությունը բացարձակ արժեքով չպետք է գերազանցի D թիվը։ Եթե ճանապարհի ընթացքում ռոբոտը պետք է հաջորդաբար անցնի a1,a2,…,ak միջանցքներով, ապա անհրաժեշտ է, որ այդ միջանցքները բավարարեն |tai - tai+1| ≤ D (i=1,2,…,k-1) պայմաններին: Սենյակների ջերմաստիճաններն անտեսվում են։ Պետք է գտնել նշված պայմաններին բավարարող ամենակարճ ճանապարհի երկարությունը տրված A և B թվերի համար։

Մուտքային տվյալներ

Առաջին տողում տրված են 3 ամբողջ թվեր՝ N, M, D (0 ≤ D ≤ 2 · 108, 2 ≤ N ≤ 1000, 1 ≤ M ≤ 1000)։
Հաջորդ M տողերում տրված են միջանցքների նկարագրությունները։ Ամեն տող պարունակում է 3 ամբողջ թիվ՝ ui, vi, ti: Սա նշանակում է, որ iրդ միջանցքը միացնում է ui և vi համարներով սենյակները, և նրա ջերմաստիճանը ti է։ Միջանցքները տրված են tiերի չնվազման կարգով։
Հաջորդ տողում տրված է Q (1 ≤ Q ≤ 10) թիվը՝ հարցումների քանակը։
Հաջորդ Q տողերում տրված են Ai և Bi (1 ≤ Ai, Bi ≤ N, Ai ≠ Bi) ամբողջ թվերը՝ ռոբոտի սկբնական և վերջնական սենյակների համարները։

Ելքային տվյալներ

Պետք է արտածել Q հատ թիվ՝ տրված Ai և Bi թվերի համար խնդրի պատասխանը։ Եթե չկա նշված պայմաններին բավարարող ճանապարհ, ապա հարկավոր է արտածել -1։

Օրինակ