問題はこちら。

時給 D が可能かどうか考える。

A, B, C, T というデータを持った道をウェイト = C - D * T の辺 (A, B)だと考えると重み付きグラフがひとつ作れる。このグラフの部分グラフであって、全域性と最小性を満たすものの辺の重さの和が 0 以下になれば時給 D が可能である。（最小全域木ではないことに注意）

ほとんどクラスカル法のアルゴリズムで求められる。具体的には辺の重みが小さい方から見ていって 

①重みが負なら付け加える 

②重みが正であっても木にするために必要なら付け加える

という操作を経て出来上がったものが最小全域グラフになる。この判定の計算量は O(M * log(M)) で可能。

あとは D について二分探索すれば O(M * log(M)) の計算量で問題が解ける。

// Union-Find木
// クラスカルの実装に便利
class UnionFind():
   def __init__(self, n):
       self.par = [i for i in range(n)]
       self.rank = [0] * n
       
   def root(self, x):
       if self.par[x] == x:
           return x
       else:
           self.par[x] = self.root(self.par[x])
           return self.par[x]
           
   def union(self, x, y):
       x = self.root(x)
       y = self.root(y)
       if x != y:
           if self.rank[x] < self.rank[y]:
               self.par[x] = y
           else:
               self.par[y] = x
               if self.rank[x] == self.rank[y]:
                   self.rank[x] += 1
                   
   def issame(self, x, y):
       return self.root(x) == self.root(y)
       
// 時給 D 以上が可能かをチェックする関数
def OK(D):
   f = lambda x:(x[0], x[1], x[2] - D*x[3])
   wes = list(map(f, es))
   wes.sort(key=lambda x:x[2])
   tot = 0
   X = UnionFind(N)
   for x, y, w in wes:
       // 木を作るのにも辺の重みを小さくするのにも必要のない辺はスルー
       if X.issame(x, y) and w >= 0:
           continue
       X.union(x, y)
       tot += w
   return tot <= 0
   
// 入力
N, M = map(int, input().split())
es = [tuple(map(int, input().split())) for _ in range(M)]

// 二分探索
ng, ok = 0, 10**6
for _ in range(30):
   D = (ok + ng) / 2
   if OK(D):
       ok = D
   else:
       ng = D
 
// 出力
print(ok)