На еден автопат се дадени K едно по друго контролни точки нумерирани со вредностите 1..K (првата точка е 1, па 2,...., а последната е K). Првата контролна точка е почетокот на автопатот.

Познати се точните растојанија меѓу N парови контролни точки.

Дадени се две контролни точки: Т₁ и Т₂. Ако е можно, најдете го растојанието меѓу контролните точки Т₁ и Т₂. Ако не е можно да се најде растојанието да се отпечати вредност -1.

Забелешка: Во најмалку 10% од тест случаите познатите растојанија ќе бидат за паровите во кои првата точка од парот секогаш е почетната точка од автопатот.

Влез

Во првиот ред се запишани два броја Т₁ и Т₂ со кои се означени две контролни точки (1<= Т₁, Т₂ <= 10 000).

Во вториот ред е запишан бројот K(1<= К<= 10 000) што го претставува бројот на контролни точки и бројот N (1<= N<= 100 000) кој го претставува бројот на познати растојанија од една до друга контролна точка.

Во секој од следните N редови се запишани три вредности одделени со празно место: P[i] K[i] D[i], i=1..N. D[i] е растојанието меѓу контролните точки нумерирани со P[i] и K[i]. (1<= P[i]≠K[i] <= 10 000; 1<=D[i] <= 10 000 000 ) .

Излез

Растојанието меѓу контролните точки Т₁ и Т₂ ако е можно да се најде. Ако растојанието не е можно да се најде, да се отпечати вредност -1.

Ограничувања

Временско ограничување: 500 milliseconds
Мемориско ограничување: 64 megabytes

Примери

влез
3 5 
6 2 
1 3 6
1 5 10

излез
4

влез
3 5
6 3
1 5 10
3 2 1
2 1 3

излез
6

влез
3 5
6 3
1 5 10
5 2 8
5 6 6

излез
-1

Објаснување за првиот тест пример: Има 6 контролни точки. Растојанието меѓу контролните точки 1 и 3 е 6 метри, а растојанието меѓу 1 и 5 е 10 метри. Растојанието меѓу точките 1 и 5 е збир на растојанието меѓу точките 1 и 3 и растојанието меѓу 3 и 5. Оттука растојанието меѓу точките 3 и 5 е 10-6=4 метри.

Објаснување за вториот тест пример: Има 6 контролни точки. Растојанието меѓу контролните точки 1 и 5 е 10 метри. 10 е збир на растојанијата меѓу точките 1 и 3 и растојанието меѓу 3 и 5. Знаеме дека растојанието од 1 до 2 е 3 метри, а од 2 до 3 е 1 метар. Оттука растојанието од 1 до 3 е 4 (=3+1) метри. Добивме дека растојанието меѓу точките 3 и 5 е разлика на растојанието меѓу точките 1 и 5 (10 метри) и 1 и 3 (4 метри). Оттука растојанието до 10-4=6 метри.

Објаснување за третиот тест пример: Познати се растојанијата меѓу точките 1 и 5, 5 и 2 како и 5 и 6. Се бара растојанието меѓу контролните точки 3 и 5. Но, од познатите растојанија не може да го најдеме бараното растојание. Затоа се печати -1.