Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int read()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,m;

#define MAXN 2510

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	return;

}

int c[MAXN],v[MAXN];

double val[MAXN];

void build(double k)

{

	for(int i = 1;i <= n;++i)val[i] = (double)v[i] - k * c[i];

	//for(int i = 1;i <= n;++i)cout << val[i] << " ";cout << endl;

	return;

}

bool vis[MAXN];

double f[MAXN][MAXN];

#define INF 10000000000

int siz[MAXN]; 

void dp(int k)

{

	vis[k] = true;siz[k] = 1;

	for(int i = 1;i <= m;++i)f[k][i] = -INF;

	f[k][0] = 0;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])continue;

		dp(e[i].to);

		siz[k] += siz[e[i].to];

		for(int j = min(siz[k],m);j >= 0;--j)

		{

			for(int l = 0;l <= j;++l)

			{

				f[k][j] = max(f[k][j],f[k][l] + f[e[i].to][j - l]);

			}

		}

	}

	for(int i = min(siz[k],m);i >= 1;--i)f[k][i] = f[k][i - 1] + val[k];

	f[k][0] = 0;//cout << k << endl;

	//for(int i = 1;i <= m;++i)cout << f[k][i] << " ";cout << endl;

	return;

}

int main()

{

	scanf("%d%d",&m,&n);++m;

	for(int i = 1;i <= n;++i)

	{

		c[i] = read();v[i] = read();

		add(read(),i);

	}

	double l = 0,r = 1000000,mid;

	for(int i = 1;i <= 40;++i)

	{

		memset(vis,false,sizeof(vis));

		mid = (l + r) / 2;

		build(mid);

		dp(0);

		if(f[0][m] > 0)l = mid;

		else r = mid;

	}

	printf("%.3lf\n",l);

	return 0;

}