$sum[i][j][k]$ 是存从 $i$ 到 $j$ 的路径上有点 $k$ 的数目

#include <iostream>
#include <cstring>
using namespace std;
#define int long long
int map[101][101], sum[101][101][101], n, m;

signed main () {
	memset (map, 0x3f, sizeof map);
	scanf ("%d %d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		map[i][i] = 0;
	}
	for (int i = 1; i <= m; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		map[a][b] = map[b][a] = c;
		sum[a][b][0] = sum[b][a][0] = 1;
	}
	for (int k = 1; k <= n; ++k) {
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= n; ++j) {
				if (map[i][j] > map[i][k] + map[k][j]) {
					map[i][j] = map[i][k] +  map[k][j];
					sum[i][j][0] = sum[i][k][0] * sum[k][j][0];
					fill (sum[i][j] + 1, sum[i][j] + 1 + n, 0);
					sum[i][j][k] += sum[i][k][0] * sum[k][j][0];
					for (int u = 1;u <= n; ++u) {
						if (i == u || j == u|| k == u) continue;
						sum[i][j][u] += sum[i][k][u] + sum[k][j][u];
					}
				} else if (map[i][j] == map[i][k] + map[k][j] && i != k && j != k) {
					sum[i][j][0] += sum[i][k][0] * sum[k][j][0];
					sum[i][j][k] += sum[i][k][0] * sum[k][j][0];
					for (int u = 1;u <= n; ++u) {
						if (i == u || u == j || k == u) continue;
						sum[i][j][u] += sum[i][k][u] + sum[k][j][u];
					}
				}
			}
		}
	}
	for (int k = 1; k <= n; ++k) {
		double ans = 0.0;
		for (int i = 1; i <= n; ++i) {
			if (i == k) continue;
			for (int j = 1; j <= n; ++j) {
				if (j == k) continue;
				if (sum[i][j][0] != 0)
					ans += sum[i][j][k] * 1.0 / sum[i][j][0];
			}
		}
		printf ("%.3f\n", ans);
	}
	return 0;
}