#include <iostream>
using namespace std;
long long x[1005], y[1005], t[1005];
long long gcd(long long a, long long b)
{
	if (b == 0) return a;
	return gcd(b, a % b);
}
int main()
{
	int n, k;
	long long ans = 21000000000;
	cin >> n >> k;
	for (int i = 1; i <= k; i++)
	{
		cin >> t[i] >> x[i] >> y[i];
	}
	for (int i = 1; i <= k; i++)
	{
		for (int j = i + 1; j <= k; j++)
		{
			long long g = gcd(t[i], t[j]);//算最大公约数
			long long f = g * (t[i] / g) * (t[j] / g);//计算最小公倍数
			long long a = t[j] / g, b = t[i] / g;
			if ((x[i] % n + (a-1) % n * y[i] % n) % n == (x[j] % n + (b-1) % n * y[j] % n) % n)//最小公倍数处是否相同
			{
				if (!(a % n * y[i] % n % n == b % n * y[j] % n % n))//判断变化量是否相同
				{
					ans = min(ans, f * 2 - 1);
				}
			}
			else
			{
				ans = min(ans, f - 1);
			}
			//cout << g << ' ' << f << endl;
		}
	}
	if (ans == 21000000000) cout << "Mystia will cook forever...";
	else cout << ans;
	return 0;
}