Description

Mr. X wants to travel from a point A(X_a, Y_a) to a point B(X_b, Y_b), A ≠ B. He has a GSM mobile phone and wants to stay available during whole the trip. A local GSM operator has installed K sets of GSM equipment in points P_i(X_i, Y_i),  1 ≤ i ≤ K. Each set of the equipment provides circular zone Z_i. Point P_i is the center of the zone Z_i and R_i is its radius. Mobile phones can operate inside such a zone and on its border. Zones can intersect, but no zone completely includes another one.

Your task is to find the length of the shortest way from A to B which is completely covered by GSM zones. You may assume that such a way always exists. Precision of calculations has to be 0.00001.

Input

The first line contains four floating point numbers X_a Y_a X_b Y_b, separated by one or more spaces. The next line contains single integer number K (K ≤ 200). Each of the rest K lines of the file contains three floating point numbers X_i, Y_i, R_i separated by one or more spaces. R_i > 0.

Output

The output has to contain a single floating point number.

0 0 8 0
2
0 4 5
8 4 5

8.24621

Source

, Western Subregion