Masala #0616

Shahzod o'z ishini yaxshi ko'radi, lekin u ofisiga borish va qaytib kelish uchun ortiqcha vaqt sarflashni yoqtirmaydi. Ko'p yillar davomida ishlagandan so'ng, u oddiy kunlarda ofisiga boradigan eng qisqa masofani biladi.

Yaqinda shaharda turli yo‘llarni muntazam ta’mirlash ishlari boshlandi. Har kuni yo'l to'sib qo'yiladi va o'sha kuni undan hech kim foydalana olmaydi, lekin boshqa barcha yo'llardan foydalanish mumkin.Har kuni siz uning ofisiga borishi mumkin bo'lgan minimal masofani aniqlashingiz kerak.

0 dan \(N-1\) gacha raqamlangan \(N\) ta shahar va \(M\) ikki yoʻnalishli yoʻllar mavjud.

Kirishning birinchi qatorida ikkita \(N, M (1 < N, M < 100000)\)
\(M\) qatorlar bo'lib, ularning har biri bo'shliqdan ajratilgan uchta \(u,v(0 \le u,v \le N−1), w(0 < w < 1001)\)
Keyingi qatorda ikkita son \(S,D( 0 \le S,D < N)\). \(S\) - Shahzod yashaydigan shahar va \(D\) - uning idorasi joylashgan shahar.
Keyingi qatorda \(Q ( 0 < Q < 21 )\)
\(Q\) satrlardan keyin har birida ikkita \(u_1\) va \(v_1\) butun sonlari mavjud bo'lib,o'sha kuni \(u_1\) va \(v_1\) o'rtasidagi yo'l to'sib qo'yilgan.

Shahzod borishi mumkin bo'lgan minimal masofani chiqaring (Har bir test uchun alohida). Agar yo'l bo'lmasa, -1 ni chop eting.