1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 300514 #define maxm 1000515 #define eps 1e-916 #define ll long long17 #define pa pair<int,int>18 using namespace std;19 inline int read()20 {21     int x=0,f=1;char ch=getchar();22     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}23     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}24     return x*f;25 }26 struct edgs{int go,next;double w,w0;}e[maxm];27 double d[maxn];28 int n,m,tot,v[maxn],head[maxn];29 bool mark[maxn],flag;30 void insert(int x,int y,double z)31 {32     e[++tot].go=y;e[tot].w0=z;e[tot].next=head[x];head[x]=tot;33 }34 void spfa(int x)35 {36     if(mark[x]){flag=1;return;}37     mark[x]=1;38     for(int i=head[x],y;i;i=e[i].next)39      if(d[x]+e[i].w<d[y=e[i].go])40       {41           d[y]=d[x]+e[i].w;42           spfa(y);43           if(flag)return;44       }45     mark[x]=0;  46 }47 bool check()48 {49     for(int i=1;i<=n;i++)d[i]=mark[i]=0;50     flag=0;51     for(int i=1;i<=n;i++)52      {53          spfa(i);54          if(flag)return 1;55      }56     return 0; 57 }58 int main()59 {60     freopen("input.txt","r",stdin);61     freopen("output.txt","w",stdout);62     n=read();m=read();63     int x,y;double z,l=inf,r=-inf,mid;64     while(m--)65      {66       x=read();y=read();scanf("%lf",&z);insert(x,y,z);67       l=min(l,z);68       r=max(r,z);69      }70     while(r-l>=eps)71      {72          mid=(l+r)/2;73          for(int i=1;i<=tot;i++)e[i].w=e[i].w0-mid;74          if(check())r=mid;else l=mid;75      }76     printf("%.8lf\n",l);  77     return 0;78 }