求证假

#include <bits/stdc++.h>
#define int long long

const int N = 1e5 + 10; 
int n, m;
struct node { int to, w; };
std::vector <node> G[N];
std::vector <int> g1[N], g2[N]; 

int dp1[N], dp2[N], in1[N], in2[N]; 


signed main() {
	
	std::cin >> n >> m;
	for (int i = 1; i <= m; ++ i) {
		int u, v, w; std::cin >> u >> v >> w;
		G[u].push_back((node) {v, w}), ++ in1[v], ++ in2[u]; 
		g1[u].push_back(v), g2[v].push_back(u); 
	}
	
	auto tps1 = [&](int s) {
		std::queue <int> q;
		dp1[s] = 1, q.push(s);
		while (!q.empty()) {
			int u = q.front(); q.pop();
			for (auto v : g1[u]) {
				dp1[v] += dp1[u];
				if (-- in1[v] == 0) q.push(v); 
			}
		}
		return void(); 
	};
	auto tps2 = [&](int s) {
		std::queue <int> q; 
		dp2[s] = 1, q.push(s);
		while (!q.empty()) {
			int u = q.front(); q.pop();
			for (auto v : g2[u]) {
				dp2[v] += dp2[u];
				if (-- in2[v] == 0) q.push(v); 
			}
		}
		return void(); 
	};
	tps1(1), tps2(n); 
	
	double ans = 0;
	for (int u = 1; u <= n; ++ u) 
		for (int i = 0; i < G[u].size(); ++ i) {
			int v = G[u][i].to, w = G[u][i].w;
			double t = 1.0 * dp1[u] * dp2[v] / dp1[n]; 
			ans += t * w; 
		}
	printf("%.2lf\n", ans); 
	
	
	return 0; 
}