Giữ kích thước lớn nhất (Get Shorty)

Nguồn: Kattis

Phiên bản: Phước Hưng OJ Extended

Đề bài

Một mê cung được mô hình hóa thành đồ thị vô hướng. Bạn bắt đầu tại giao điểm $0$ và muốn tới giao điểm $n-1$.

Mỗi hành lang có một hệ số $f$ với $0<f\le1$. Khi đi qua hành lang, kích thước hiện tại bị nhân với $f$.

Nếu đi qua các hành lang có hệ số $f_1,f_2,\ldots,f_k$, phần kích thước còn lại là

Hãy chọn đường đi để phần kích thước còn lại là lớn nhất. Đề bảo đảm luôn có đường từ giao điểm $0$ đến giao điểm $n-1$.

Input

Dòng đầu chứa hai số nguyên $n,m$.

Trong $m$ dòng tiếp theo, mỗi dòng chứa $x,y,f$, mô tả một hành lang hai chiều giữa $x$ và $y$. Giá trị $f$ có nhiều nhất bốn chữ số sau dấu thập phân.

Các giao điểm được đánh số từ $0$ đến $n-1$.

Output

In phần kích thước lớn nhất còn lại khi đến giao điểm $n-1$, với đúng bốn chữ số sau dấu thập phân.

Subtask

Trong tất cả các Subtask: $2<n<10^4$; $1<m<1.5\cdot10^4$; $0\le x,y<n$; $0<f\le1$; $f$ có nhiều nhất bốn chữ số sau dấu thập phân; luôn tồn tại đường từ $0$ đến $n-1$.

• Subtask 1 — 10%: Mọi hành lang có cùng một hệ số $f$.
• Subtask 2 — 20%: Đồ thị là một cây, tức $m=n-1$.
• Subtask 3 — 30%: $n\le300$; $m\le1500$.
• Subtask 4 — 40%: Không có điều kiện bổ sung.

Ví dụ

Input

3 3
0 1 0.9
1 2 0.9
0 2 0.8

Output

0.8100

Giải thích

Đường $0\to1\to2$ giữ lại $0.9\cdot0.9=0.81$, lớn hơn đường trực tiếp chỉ giữ $0.8$. Vì vậy kết quả là 0.8100.