Làng Đo Đo là một ngôi làng nhỏ nằm ven con sông Kiếp Bạc. Làng gồm ~N~ xóm, các xóm được nối với nhau bởi ~N-1~ con đường hai chiều, sao cho từ một xóm có thể đi tới một xóm khác bất kỳ.

Có dịp về làng Đo Đo chơi vài ngày, Đông định cùng cô bạn Rùa của mình đi chơi khắp làng xóm để thỏa nỗi nhớ mong xa cách. Nhưng thật không may, một trận mưa lớn vừa xảy ra ở làng, và do hệ thống thoát nước chống ngập của làng Đo Đo không được trùng tu bảo dưỡng, một số con đường của làng có thể đã bị ngập.

Đông muốn cùng cô bạn Rùa đi chơi càng xa càng tốt (để đỡ bị cô Út Huệ hay bà ngoại Rùa gọi về), vì vậy anh ta muốn biết khoảng cách trung bình từ nhà của Rùa (là địa điểm xuất phát), tới nơi xa nhất tới được. Biết nhà của rùa nằm ở xóm ~1~, và độ dài mỗi con đường đều là ~1~.

Do đã sơ suất để quên Ipod, Itouch, Iphone, Ipad, Iwatch, ...ở Sài Gòn, anh chàng Đông cần nhờ tới sự giúp đỡ của các thí sinh VM15.

Input

Dòng đầu tiên gồm ~1~ số nguyên dương ~N~, là số xóm trong làng.

~N-1~ dòng tiếp theo, mỗi dòng gồm ~3~ số nguyên ~u~ ~v~ ~p~ mô tả một con đường, bao gồm ~2~ xóm đầu cuối ~(u~, ~v)~ và xác suất ~(p)~ con đường không bị ngập sau trận mưa (tính theo phần trăm).

Output

In ra khoảng cách trung bình từ nhà của Rùa (xóm ~1~) tới xóm xa nhất có thể tới được, với ít nhất ~6~ chữ số sau dấu phẩy.

Giới hạn

• Trong tất cả các test ~0 \leq p \leq 100~
• Subtask1: ~N \leq 15~ ~(25\%~ số điểm)
• Subtask2: ~N \leq 2207~ ~(31.25\%~ số điểm)
• Subtask3: ~N \leq 97722, p \leq 97~ ~(43.75\%~ số điểm)

Sample Input 1

4
1 2 50
2 3 50
1 4 50

Sample Output 1

1.000000000

Sample Input 2

3
1 2 33
1 3 66

Sample Output 2

0.772200000

Note

Test Ví dụ 1

Nếu ~2~ con đường (~1~, ~2~) và (~2~, ~3~) đều không bị ngập (xác suất ~25\%~), độ dài đường đi là ~2~.

Nếu ~2~ con đường (~1~, ~2~) và (~1~, ~4~) đều bị ngập (xác suất ~25\%~), độ dài đường đi là ~0~.

Các trường hợp còn lại (xác suất ~50\%~), độ dài đường đi là ~1~.

Vậy độ dài trung bình là ~(0.25 \times 2 + 0.25 \times 0 + 0.5 \times 1) = 1~.

Test Ví dụ 2

Nếu ~1~ trong ~2~ con đường ~k~ bị ngập, độ dài đường đi là ~1~, ngược lại độ dài đường đi là ~0~.

Xác suất để cả ~2~ con đường đều bị ngập là ~(100\%-33\%) \times (100\%-66\%) = 22.78\%~