1 /**************************************************************  2     Problem: 1486  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:284 ms  7     Memory:1156 kb  8 ****************************************************************/  9   10 #include <cstdio> 11 #include <cstring> 12   13 using namespace std; 14 typedef double lf; 15 const int N = 3005; 16 const int M = 10005; 17 const int inf = 1e9; 18 const lf eps = 1e-10; 19   20 inline int read() { 21     int x = 0, sgn = 1; 22     char ch = getchar(); 23     while (ch < ‘0‘ || ‘9‘ < ch) { 24         if (ch == ‘-‘) sgn = -1; 25         ch = getchar(); 26     } 27     while (‘0‘ <= ch && ch <= ‘9‘) { 28         x = x * 10 + ch - ‘0‘; 29         ch = getchar(); 30     } 31     return sgn * x; 32 } 33   34 struct Edge { 35     int x, y; 36     lf v; 37       38     inline void Read() { 39         x = read(), y = read(); 40         scanf("%lf", &v); 41     } 42 } E[M]; 43   44 struct edge { 45     int next, to; 46     lf v; 47     edge() {} 48     edge(int _n, int _t, lf _v) : next(_n), to(_t), v(_v) {} 49 } e[M]; 50   51 int n, m; 52 int first[N], tot; 53 lf d[N]; 54 bool f, v[N]; 55   56 inline void add_edge(int x, int y, lf v) { 57     e[++tot] = edge(first[x], y, v); 58     first[x] = tot; 59 } 60   61 void spfa(int p) { 62     int x, y; 63     v[p] = 1; 64     for (x = first[p]; x; x = e[x].next) 65         if (d[p] + e[x].v < d[y = e[x].to]) { 66             if (v[y]) { 67                 f = 1; 68                 break; 69             } else 70                 d[y] = d[p] + e[x].v, spfa(y); 71         } 72     v[p] = 0; 73 } 74   75 void build_graph(lf x) { 76     int i; 77     tot = 0, memset(first, 0, sizeof(first)); 78     for (i = 1; i <= m; ++i) 79         add_edge(E[i].x, E[i].y, E[i].v - x); 80 } 81   82 bool check(lf x) { 83     int i; 84     build_graph(x); 85     memset(v, 0, sizeof(v)), memset(d, 0, sizeof(d)); 86     for (i = 1, f = 0; i <= n; ++i) { 87         spfa(i); 88         if (f) return 1; 89     } 90     return 0; 91 } 92   93 int main() { 94     int i; 95     scanf("%d%d", &n, &m); 96     for (i = 1; i <= m; ++i) 97         E[i].Read(); 98     lf l = -inf, r = inf, mid; 99     while (l + eps < r) {100         mid = (l + r) / 2;101         if (check(mid)) r = mid; else l = mid;102     }103     printf("%.8lf\n", l);104     return 0;105 }