rt，蒟蒻第一次打spfa，可能写的有点丑，求谅解QwQ

#include<bits/stdc++.h>
#define ll long long
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
double n,m,f[5005],u,v,t[5005],l,r=114514,mid,ans;
double dis[5005];
struct node{int v,w,id;};
vector<node>e[1005];
int cnt[1005];
bool vis[1005];
bool spfa(int x){
	mem(dis,0x3f),mem(vis,0),mem(cnt,0);
	queue<int>q;
	vis[x]=1,dis[x]=0,q.push(x);
	while(q.size()){
		int X=q.front();
		q.pop(),vis[X]=0;
		for(auto y:e[X]){
			int Y=y.v,W=y.w;
			if(dis[Y]>dis[X]+W){
				dis[Y]=dis[X]+W;
				cnt[Y]=cnt[X]+1;
				if(cnt[Y]>=n)return 1;
				if(!vis[Y])q.push(Y),vis[Y]=1;
			}
		}
	}
	return 0;
}
bool check(double x){
	fo(i,1,n)
		for(auto &j:e[i])j.w=t[j.id]*x-f[i];
	fo(i,1,n)
		if(spfa(i))return 1;
	return 0;
}
int main(){
	cin>>n>>m;
	fo(i,1,n)cin>>f[i];
	fo(i,1,m){
		cin>>u>>v>>t[i];
		node pp;
		pp.v=v,pp.w=t[i],pp.id=i;
		e[(int)u].push_back(pp);
	}
	while(r-l>1e-4){
		mid=(l+r)/2;
		if(check(mid))ans=l=mid;
		else r=mid;
	}
	printf("%.2lf",ans);
	return 0;
}