tmt.cpp

// by tmt514
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <string>
#include <vector>
#define SZ(x) ((int)(x).size())
#define FOR(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)
using namespace std;
typedef long long LL;

const int N = 5005;
const int M = 100005;
int s[M], t[M], c[M], p[M], q[M];
#include <iomanip>
#include <queue>
#include <cassert>
//#define NDEBUG
//int Q[5000005], qb, qe;
#include <queue>
priority_queue<pair<double, int>> PQ;
void solve() {
	int n, m;
	vector<int> a[N];
	const double INF = 1e9;
	double d[N];
	scanf("%d%d", &n, &m);
	assert(m <= 100000);
	for(int i=0;i<m;i++) {
		scanf("%d%d%d%d%d", &s[i], &t[i], &c[i], &p[i], &q[i]);
		assert(1 <= s[i] && s[i] <= n);
		assert(1 <= t[i] && t[i] <= n);
		assert(1 <= c[i] && c[i] <= 100);
		assert(1 <= p[i] && p[i] <= 100);
		assert(1 <= q[i] && q[i] <= 100);
		assert(s[i] != t[i]);
		a[s[i]].push_back(i);
		a[t[i]].push_back(i);
	}
	for(int x=1;x<=n;x++) {
		d[x] = INF;
		for(auto i: a[x]) {
			int pmiss = 100 - (x == s[i]? p[i]: q[i]);
			int qmiss = 100 - (x == s[i]? q[i]: p[i]);
			d[x] = min(d[x], c[i] * (10000 + 100 * pmiss) / (double)(10000 - pmiss * qmiss));
		}
	}
	
	bool mark[N] = {};
	//qb = qe = 0;
	for(int x=1;x<=n;x++) { mark[x] = 1; PQ.push({ -d[x], x }); }
	while (!PQ.empty()) {
		auto pp = PQ.top();
		PQ.pop();
		int x = pp.second;
		//int x = Q[qb++];
		mark[x] = false;
		for(auto i : a[x]) {
			int y = (x==s[i]? t[i]: s[i]);
			int pmiss = 100 - (x == s[i]? p[i]: q[i]);
			double v = c[i] + pmiss / 100.0 * d[y];
			if (d[x] > v) d[x] = v;
		}
		for(auto i : a[x]) {
			int y = (x==s[i]? t[i]: s[i]);
			int qmiss = 100 - (x == s[i]? q[i]: p[i]);
			double v = c[i] + qmiss / 100.0 * d[x];
			if (d[y] > v) {
				d[y] = v;
				if (mark[y] == false) {
					mark[y] = true;
					PQ.push({ -d[y], y });
					//Q[qe++] = y;
				}
			}
		}
	}

	for(int i=0;i<m;i++) {
		int x = s[i], y = t[i];
		//fprintf(stderr, "x=%d (%.6Lf), y=%d (%.6Lf), (c=%d, p=%d, q=%d)\n", x, d[x], y, d[y], c[i], p[i], q[i]); 
		assert(d[x] <= c[i] + (100-p[i]) / 100.0 * d[y]);
		assert(d[y] <= c[i] + (100-q[i]) / 100.0 * d[x]);
	}
	
	cout << fixed << setprecision(6) << d[1] << endl;
}

int main(void) {
	int T;
	srand(0);
	scanf("%d", &T);
	while(T--) solve();
  return 0;
}