Problem: Vampire

Mr. C is a vampire. If he is exposed to the sunlight directly, he turns into ash. Nevertheless, last night, he attended to the meeting of Immortal and Corpse Programmers Circle, and he has to go home in the near dawn. Fortunately, there are many tall buildings around Mr. C's home, and while the sunlight is blocked by the buildings, he can move around safely. The top end of the sun has just reached the horizon now. In how many seconds does Mr. C have to go into his safe coffin?

To simplify the problem, we represent the eastern dawn sky as a 2-dimensional x-y plane, where the x axis is horizontal and the y axis is vertical, and approximate building silhouettes by rectangles and the sun by a circle on this plane.

The x axis represents the horizon. We denote the time by t, and the current time is t=0. The radius of the sun is r and its center is at (0, -r) when the time t=0. The sun moves on the x-y plane in a uniform linear motion at a constant velocity of (0, 1) per second.

The sunlight is blocked if and only if the entire region of the sun (including its edge) is included in the union of the silhouettes (including their edges) and the region below the horizon (y ≤ 0).

Write a program that computes the time of the last moment when the sunlight is blocked.

The following figure shows the layout of silhouettes and the position of the sun at the last moment when the sunlight is blocked, that corresponds to the first dataset of Sample Input below. As this figure indicates, there are possibilities that the last moment when the sunlight is blocked can be the time t=0.


<image>


The sunlight is blocked even when two silhouettes share parts of their edges. The following figure shows the layout of silhouettes and the position of the sun at the last moment when the sunlight is blocked, corresponding to the second dataset of Sample Input. In this dataset the radius of the sun is 2 and there are two silhouettes: the one with height 4 is in -2 ≤ x ≤ 0, and the other with height 3 is in 0 ≤ x ≤ 2.


<image>


Input

The input consists of multiple datasets. The first line of a dataset contains two integers r and n separated by a space. r is the radius of the sun and n is the number of silhouettes of the buildings. (1 ≤ r ≤ 20, 0 ≤ n ≤ 20)

Each of following n lines contains three integers xli, xri, hi (1 ≤ i ≤ n) separated by a space.

These three integers represent a silhouette rectangle of a building. The silhouette rectangle is parallel to the horizon, and its left and right edges are at x = xli and x = xri, its top edge is at y = hi, and its bottom edge is on the horizon. (-20 ≤ xli < xri ≤ 20, 0 < hi ≤ 20)

The end of the input is indicated by a line containing two zeros separated by a space.

Note that these silhouettes may overlap one another.

Output

For each dataset, output a line containing the number indicating the time t of the last moment when the sunlight is blocked. The value should not have an error greater than 0.001. No extra characters should appear in the output.

Sample Input


2 3
-2 -1 3
0 1 3
2 3 3
2 2
-2 0 4
0 2 3
2 6
-3 3 1
-2 3 2
-1 3 3
0 3 4
1 3 5
2 3 6
2 6
-3 3 1
-3 2 2
-3 1 3
-3 0 4
-3 -1 5
-3 -2 6
0 0


Output for the Sample Input


0.0000
3.0000
2.2679
2.2679






Example

Input

2 3
-2 -1 3
0 1 3
2 3 3
2 2
-2 0 4
0 2 3
2 6
-3 3 1
-2 3 2
-1 3 3
0 3 4
1 3 5
2 3 6
2 6
-3 3 1
-3 2 2
-3 1 3
-3 0 4
-3 -1 5
-3 -2 6
0 0


Output

0.0000
3.0000
2.2679
2.2679

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;
import java.lang.ArrayIndexOutOfBoundsException;
import java.math.*;


class Main {
	static Scanner sc = new Scanner(new InputStreamReader(System.in));
	public static void main(String[] args) throws Exception {
		try{
		while(true) {
			int r = sc.nextInt();
			int n = sc.nextInt();
			if(r+n == 0) break;
			System.out.printf("%.4f\n", solve(r, n));
		}
		} catch(Exception e) {
			System.out.println(e);
		}
	}
	
	
	static double solve(int r, int n) {
		int[] dp = new int[40];
		HashMap<int[], Integer> map = new HashMap<int[], Integer>();
		for (int i = 0; i < n; i++) {
			int xl = sc.nextInt();
			int xr = sc.nextInt();
			int h = sc.nextInt();
			for(int j = xl; j < xr; j++) {
				int index = j + 20;
				dp[index] = Math.max(dp[index], h);
			}
		}
		// System.out.println(Arrays.toString(dp));
		
		for(double ans = -r; ans < 20.0; ans += 0.0005) {
			for (int i = 1-r; i < r; i++) {
				int index = i + 20;
				int h = Math.min(dp[index-1], dp[index]);
				// System.out.println(index + " "+ h);
				double dist = sqdist(0.0, ans, (double)i, (double)h);
				if(dist < (double)(r*r)) {
					return ans + (double)r;
				}
			}
		}
		return 0.0;
	}
	public static int sq(int i) {
		return i * i;
	}

	public static double sq(double d) {
		return d * d;
	}
	// square を snippet から実装してください
	public static int sqdist(int x1, int y1, int x2, int y2) {
		return sq(x1 - x2) + sq(y1 - y2);
	}

	public static double sqdist(double x1, double y1, double x2, double y2) {
		return sq(x1 - x2) + sq(y1 - y2);
	}

	public static double dist(int x1, int y1, int x2, int y2) {
		return Math.sqrt(sqdist(x1, y1, x2, y2));
	}

	public static double dist(double x1, double y1, double x2, double y2) {
		return Math.sqrt(sqdist(x1, y1, x2, y2));
	}
}



/**
 * 複素数
 */
class Complex {
	static Complex I = new Complex(0, 1);

	double r = 0.0;
	double i = 0.0;
	Complex(double r, double i) {
		this.r = r;
		this.i = i;
	}

	/**
	 * 和
	 */
	public Complex add(Complex a) {
		return new Complex(r * a.r, i + a.i);
	}

	/**
	 * 積
	 */
	public Complex mul(Complex a) {
		return new Complex(
				r * a.r - i * a.i,
				r * a.i + i * a.r);
	}

	public Complex divide(double a) {
		return new Complex(r/a, i/a);
	}

	public Complex inverse() {
		double b = 1 / (r*r + i*i);
		return new Complex(r/b, -i/b);
	}


	@Override
	public String toString(){
		return r + "+" + i + "i";
	}
}




// --- ここから下はライブラリ ----------
/**
 * MyUtil
 * @author yoshikyoto
 */
class MyIO {
	public static int toInt(boolean[] a){
		int pow = 1, ret = 0, l = a.length;
		for(int i = 0; i < l; i++){
			if(a[i]) ret += pow;
			pow *= 2;
		}
		return ret;
	}
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static int ins[];
	public static int[] readIntMap() throws IOException{return parseInt(readLine().split(" "));}
	public static int readIntMap(int i) throws Exception{
		if(i == 0) ins = readIntMap();
		return ins[i];
	}
	public static int[][] readIntMap(int n, int m) throws IOException{
		int[][] ret = new int[n][];
		for(int i = 0; i < n; i++) ret[i] = readIntMap();
		return ret;
	}
	public static int[] readIntToMap(int n) throws IOException{
		int[] ret = new int[n];
		for(int i = 0; i < n; i++) ret[i] = readInt();
		return ret;
	}
	public static int[] readNoDistIntMap() throws IOException{
		String[] strs = readLine().split("");
		int l = strs.length;
		int[] ret = new int[l-1];
		for(int i = 1; i < l; i++)
			ret[i-1] = parseInt(strs[i]);
		return ret;
	}
	public static String readLine() throws IOException{return br.readLine();}
	public static int readInt() throws IOException{return Integer.parseInt(br.readLine());}
	public static int[] parseInt(String[] arr){
		int[] res = new int[arr.length];
		for(int i = 0; i < arr.length; i++)res[i] = Integer.parseInt(arr[i]);
		return res;
	}
	public static double[] parseDouble(String[] arr){
		double[] res = new double[arr.length];
		for(int i = 0; i < arr.length; i++)res[i] = Double.parseDouble(arr[i]);
		return res;
	}
	public static boolean[] parseBool(String[] arr){
		int[] t = parseInt(arr);
		boolean[] res = new boolean[t.length];
		for(int i = 0; i < t.length; i++){
			if(t[i] == 1){res[i] = true;
			}else{res[i] = false;}
		}
		return res;
	}
	public static int parseInt(Object o){
		return Integer.parseInt(o.toString());
	}
}