思路：以val[u]-ans*edge[i].len最为边权，判断是否有正环存在，若有，那么就是ans小了。否则就是大了。
在spfa判环时，先将所有点进队列。
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cmath>
#define Maxn 1010
#define Maxm 6000
#define inf 1e10
#define eps 1e-4
using namespace std;
int vi[Maxn];
struct Edge{
int u,v,next;
double len;
}edge[Maxm];
double dis[Maxn],val[Maxn];
int head[Maxn],e,n,cnt[Maxn];
void add(int u,int v,double len)
{
edge[e].u=u,edge[e].v=v,edge[e].len=len,edge[e].next=head[u],head[u]=e++;
}
void init()
{
e=;
memset(vi,,sizeof(vi));
memset(cnt,,sizeof(cnt));
memset(head,-,sizeof(head));
}
int spfa(double ans)
{
int i,j,v,u;
queue<int> q;
memset(cnt,,sizeof(cnt));
for(i=;i<=n;i++){
dis[i]=;
q.push(i);
vi[i]=;
}
while(!q.empty()){
int u=q.front();
cnt[u]++;
q.pop();
vi[u]=;
for(i=head[u];i!=-;i=edge[i].next){
v=edge[i].v;
double d=val[u]-ans*edge[i].len;
if(dis[v]<dis[u]+d){
dis[v]=dis[u]+d;
cnt[v]++;
if(cnt[v]>=n) return ;
if(!vi[v]){
q.push(v);
vi[v]=;
}
}
}
}
return ;
}
int main()
{
int i,j,a,b,m;
double c;
while(scanf("%d%d",&n,&m)!=EOF){
init();
for(i=;i<=n;i++)
scanf("%lf",val+i);
for(i=;i<=m;i++){
scanf("%d%d%lf",&a,&b,&c);
add(a,b,c);
}
double l=,r=,mid;
while(r-l>eps){
mid=(l+r)/;
if(spfa(mid))
l=mid;
else
r=mid;
}
printf("%.2lf\n",l);
}
return ;
}