## Editorial for Vận chuyển hàng

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#include <bits/stdc++.h>
#define ii pair<int, int>
#define iii pair<int, ii>
#define X first
#define Y second
const int N = 111;
const double eps = 1e-4;
using namespace std;
vector<iii> e;
int n, m;
double d[N];

bool Relax(iii e, double w) {
bool ret = d[e.Y.X] + e.X - w < d[e.Y.Y];
if (ret)
d[e.Y.Y] = d[e.Y.X] + e.X - w;
return ret;
}

bool NC_exist(double avg) {
//check if there is a negative cycle using BellmanFord Alg
//each edge is decreased by avg
int i, j; bool stop;
for(i = 1; i <= n; i++) d[i] = 0;
for(i = 1; i < n; i++) {
stop = true;
for(j = 0; j < m; j++)
if (Relax(e[j], avg))
stop = false;
if (stop) break;
}
for(j = 0; j < m; j++)
if (Relax(e[j], avg)) return true;
return false;
}

int main()
{
//freopen("QBTRANS.in", "r", stdin);
scanf("%d %d\n", &n, &m);
int i, u, v, c;
for(i=0; i<m; i++) {
scanf("%d %d %d\n", &u, &v, &c);
e.push_back(iii(c, ii(u, v)));
}
double l = 0, r = 1e9, mid, res = -1;
while (r - l > eps) {
mid = (l + r) / 2;
if (NC_exist(mid)) {
res = mid;
r = mid;
}
else
l = mid;
}
if (res < 0 || res > 1e8) printf("-1");
else printf("%.2f", res);
return 0;
}


#### Code mẫu của RR

//Written by Nguyen Thanh Trung
{$R-,Q-} {$Mode objFPC}
uses math;
const
FINP          =       '';
FOUT          =       '';
MAXN          =       111;
gh            =       10;
eps           =       5e-3;
oo            =       1000111000;
type
real          =       extended;
Tedge         =       record u,v,c:longint; end;
var
f1,f2         :       text;
n,m           :       longint;
edge          :       array[1..MAXN*MAXN] of Tedge;
d             :       array[1..MAXN] of real;
trace         :       array[1..MAXN] of longint;

procedure openF;
begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
close(f1);
close(f2);
end;
procedure inp;
var
i:longint;
begin
for i:=1 to m do
end;
function check(val:real):boolean; inline;
var
found:boolean;
i,nn:longint;
begin
fillchar(d,sizeof(d),0);

for nn:=1 to gh do
begin
fillchar(trace,sizeof(trace),0);
found:=false;
for i:=1 to m do
with edge[i] do
if d[v]>d[u]+c-val+eps then
begin
trace[v]:=u;
d[v]:=d[u]+c-val;
found:=true;
end;
end;
exit(false);
end;
function findMax:longint;
var
i,kq:longint;
begin
kq:=0;
for i:=1 to m do
kq:=max(kq,edge[i].c);
exit(kq);
end;
procedure solve;
var
l,r,mid,kq:real;
begin
kq:=-1; l:=0; r:=findMax+eps;
while l<r do
begin
mid:=(l+r)/2;
if not check(mid) then
begin
kq:=mid;
r:=mid-eps;
end
else l:=mid+eps;
end;
if check(kq) then begin end;
if kq=-1 then writeln(f2,kq:0:0)
else writeln(f2,trunc(kq*100)/100:0:2);
end;

begin
openF;
inp;
solve;
closeF;
end.


#### Code mẫu của khuc_tuan

#include <iostream>
#include <queue>
using namespace std;

int n, m;
int a[111][111];
double d[111];
bool inq[111];
int step[111];

int main() {
scanf("%d%d", &n, &m);
for(int i=0;i<m;++i) {
int u, v, c;
scanf("%d%d%d", &u, &v, &c);
if(a[u][v]==0) a[u][v] = c;
else a[u][v] <?= c;
}
double left = 0, right = 1e7;
for(int kk=0;kk<40;++kk) {
double mid = (left+right) / 2;
queue<int> q;
for(int i=1;i<=n;++i) d[i] = 0, q.push(i);
memset( inq, true, sizeof(inq));
memset( step, 0, sizeof(step));
bool OK = false;
while(!q.empty()) {
int u = q.front(); q.pop();
inq[u] = false;
for(int v=1;v<=n;++v) if(a[u][v] > 0 && d[v] > d[u] + a[u][v] - mid) {
d[v] = d[u] + a[u][v] - mid;
step[v] = step[u] + 1;
if(step[v] >= n + 3) {
OK = true;
goto lab;
}
if(!inq[v]) {
inq[v] = true;
q.push(v);
}
}
}
lab : ;
if(OK) right = mid;
else left = mid;
}
//  cout << left << " " << right << endl;
if(left > 1e7 - 2) cout << -1 << endl;
else printf("%.2f\n", left);
// system("pause");
return 0;
}