POLSKI SPOJ

Jasio otrzymał telefon od przyjaciela. Przyjaciel ten zaprasza go na kręgle. Kręgle znajdują się na skrzyżowaniu B, a Jasio siedzi w swoim domu znajdującym się przy skrzyżowaniu A. Jasiu ma mapę miasta na której znajduje się N skrzyżowań oraz M dróg łączących te skrzyżowania. Każda droga na mapie ma określoną długość. Jasio bardzo łatwo gubi się w mieście, dlatego zastanawia się, jaka jest oczekiwana długość* drogi z jego domu do kręgielni, jeśli weźmie pod uwagę tylko takie drogi, w których przez każde skrzyżowanie przejdzie maksymalnie raz.

Pomóż mu!

*Wartość oczekiwana

Input

Pierwsza linia - N, M (1 ≤ N ≤ 20, N ≤ M ≤ 40) - oznaczają kolejno liczbę skrzyżowań, oraz liczbę dróg.

Kolejne M linii zawiera a_i, b_i, v_i (1 ≤ a_i,b_i,v_i ≤ N, a_i != b_i) oznaczające, że istnieje droga od skrzyżowania a_i do skrzyżowania b_i o długości v_i. Każda droga jest dwukierunkowa. Drogi mogą tworzyć cykle. Nie istnieją dwie drogi łączące dwa te same skrzyżowania. Nie istnieje droga łącząca jedno i to samo skrzyżowanie.

Ostatnia linia zawiera liczbę A oraz B (1 ≤ A, B ≤ N) - kolejno: skrzyżowanie przy którym jest dom Jasia, oraz skrzyżowanie przy którym znajduje się kręgielnia.

Output

Jedna liczba X (z precyzją ustawioną do 10^-6) oznaczająca oczekiwaną długość drogi z domu Jasia do kręgielni. Jeśli nie ma takiej drogi, na wyjściu powinna pojawić się jedna liczba, -1.

Przykład

Wejście:
5 6

1 2 1

2 3 3

1 3 2

3 4 5

2 5 4

4 5 6

1 5

Wyjście:
10.500000

Wyjaśnienie:

Istnieją 4 możliwe drogi z punktu 1 do punktu 5:

1 -> 2 -> 5 (koszt 5)

1 -> 2 -> 3 -> 4 -> 5 (koszt 15)

1 -> 3 -> 4 -> 5 (koszt 13)

1 -> 3 -> 2 -> 5 (koszt 9)

Oczekiwana długość drogi = (5+15+13+9)/4 = 10.5