Most Comfortable Route

Z Town is a picturesque location that attracts tourists from everywhere. There are \( n \) scenic spots (numbered \( 1,2,3,\ldots,n \)) around Z Town which are connected by \( m \) bidirectional roads. There might be multiple roads between two spots. In order to protect its tourism resources, Z Town enforces a strange regulation: on any given road \( r_i \), vehicles must travel at an exact speed of \( v_i \).

Since abrupt speed changes cause discomfort, when traveling from one scenic spot to another, tourists want to choose a route where the ratio between the maximum speed and the minimum speed encountered is minimized. In other words, if a route uses roads with speeds \( s_1, s_2, \ldots, s_k \), they wish to minimize the value of

\( \frac{\max\{s_1, s_2, \ldots, s_k\}}{\min\{s_1, s_2, \ldots, s_k\}} \)

Your task is to help determine the minimum possible ratio on a route from spot 1 to spot \( n \). If no such route exists, output -1.

inputFormat

The first line contains two integers \( n \) and \( m \) separated by a space, representing the number of scenic spots and the number of roads, respectively.

The following \( m \) lines each contain three integers \( u \), \( v \) and \( v_i \) separated by spaces, indicating that there is a bidirectional road connecting spot \( u \) and spot \( v \) with a fixed speed of \( v_i \).

outputFormat

If there exists a route from spot 1 to spot \( n \) then print the minimum possible ratio of the maximum speed to the minimum speed encountered along the route, rounded to 6 decimal places. Otherwise, output -1.

sample

3 3
1 2 10
2 3 20
1 3 15

1.000000