rt

#include <bits/stdc++.h>
using namespace std;
int l,p,f[5005],cnt[5005];
double dis[5005];
vector <int> v[5005],w[5005],zs[5005];
bool vis[5005];
queue <int> q;
bool check(double m)
{
	memset(dis,0,sizeof(dis));
	memset(vis,true,sizeof(vis));
    for (int i=1;i<=l;i++)
    {
    	dis[i]=0;
    	vis[i]=1;
    	q.push(i);
    	cnt[i]=0;
    }
    while (!q.empty())
    {
    	int fr=q.front();
    	q.pop();
    	vis[fr]=false;
    	for (int i=0;i<v[fr].size();i++)
    	{
    		int mb=v[fr][i],longs=w[fr][i];
    		if (dis[mb]<dis[fr]+(m*longs-zs[fr][i]))
    		{
    			cnt[mb]=cnt[fr]+1;
    			dis[mb]=dis[fr]+(m*longs-zs[fr][i]);
    			if (cnt[mb]>=l)
    			{
    				return true;
    			}
    			if (!vis[mb])
    			{
    				q.push(mb);
    				vis[mb]=true;
    			}
    		}
    	}
    }
    return false;
}
int main()
{
	cin>>l>>p;
	for (int i=1;i<=p;i++)
	{
		int x,y,z,s;
		cin>>x>>y>>z>>s;
		v[x].push_back(y);
		w[x].push_back(z);
		zs[x].push_back(s);
	}
	double leftt=0,rightt=2000;
	while (rightt-leftt>0.001)
	{
		double mid=(leftt+rightt)/2;
		if (check(mid))
		{
			leftt=mid;
		}
		else
		{
			rightt=mid;
		}
	}
	if (leftt==0)
	{
		cout<<-1;
		return 0;
	}
	printf("%.1f",leftt);
	return 0;
}

20分