Условие

---

F. СНЯГ
---
Планинска област има N населени места, номерирани с целите числа от 1 до N. Двупосочни пътни отсечки свързват пряко М двойки от тях, така че от всяко населено място може да се стигне до всяко друго. Районът е прочут с това, че при зимни условия използването на пътищата не винаги е възможно. За да осигури колкото е възможно по-стабилен трафик през зимата, областният директор на Агенция „Пътища“ поръчал да се направи изследване на надеждността на отделните пътни отсечки. В резултат от наблюденията на пътищата, специалистите му представили списък, в който на всяка пътна отсечка било присвоено цяло число R между 10 и 900 включително – надеждност на отсечката, което означава, че след падане на обилен сняг се очаква в R от 1000 случая пътната отсечка да е проходима, а в останалите 1000 – R  да не е. Това обаче не било достатъчно за шофьорите. Когато шофьор трябвало да пътува от населеното място A към населено място B, той искал да му посочат очаквания най-надежден път от A до B. Напишете програма, която по зададени надеждности на пътищата да определя най-надеждния път между две зададени населени места.

Вход: 
Програмата трябва да може да обработва няколко примера при едно изпълнение. На първия ред на стандартния вход ще бъде зададен броят T на тестовите примери. Всеки тестов пример започва с ред, на който ще бъдат зададени числата N и M. На всеки от следващите M реда ще бъдат зададени двете населени места, които поредната пътна отсечка свързва и нейната надеждност. На последния ред за теста ще бъдат зададени A и B, за които се търси  най-надежден път.  

Изход: 
За всеки тестов пример програмата трябва да изведе на eдин ред на стандартния изход редица от номера на населени места, започваща с A и завършваща с B – населените места по един най-надежден път от A до B. 

Ограничения: 
5 ≤ N ≤ 1000.

Примерен вход: 
1
6 9
1 2 200
1 3 100
1 6 250
2 3 700
3 6 200
3 4 100
4 6 900
4 5 800
5 6 600
1 4	

Примерен изход:
1 6 4