#include<bits/stdc++.h>
using namespace std;
long long dis1[100005],dis2[100005];
bool vis[100005];
struct stu{
int x,w;
};
long long a[100005],b[100005];
vector<stu>v[100005];
struct stu2{
long long x,w;
inline bool friend operator<(stu2 const &a,stu2 const &b)
{
return a.w>b.w;
}
};
priority_queue<stu2>q;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin>>t;
while(t--)
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
v[i].clear();
}
memset(dis1,0x3f,sizeof(dis1));
memset(dis2,0x3f,sizeof(dis2));
for(int i=1;i<=m;i++)
{
int x,y,w;
cin>>x>>y>>w;
v[x].push_back({y,w});
v[y].push_back({x,w});
}
dis1[1]=0;
q.push({1,0});
while(!q.empty())
{
int x=q.top().x;
q.pop();
vis[x]=0;
for(auto i:v[x])
{
if(dis1[i.x]>dis1[x]+i.w)
{
dis1[i.x]=dis1[x]+i.w;
if(!vis[i.x])
{
vis[i.x]=1;
q.push({i.x,dis1[i.x]});
}
}
}
}
dis2[2]=0;
q.push({2,0});
while(!q.empty())
{
int x=q.top().x;
q.pop();
vis[x]=0;
for(auto i:v[x])
{
if(dis2[i.x]>dis2[x]+i.w)
{
dis2[i.x]=dis2[x]+i.w;
if(!vis[i.x])
{
vis[i.x]=1;
q.push({i.x,dis2[i.x]});
}
}
}
}
for(int i=1;i<=n;i++)
{
a[i]=dis1[i]+dis2[i];
b[i]=dis1[i]-dis2[i];
}
sort(a+1,a+n+1);
sort(b+1,b+n+1);
long long sum=0;
int xx=a[(n+1)/2],yy=b[(n+1)/2];
for(int i=1;i<=n;i++)
{
sum+=abs(xx-a[i])+abs(yy-b[i]);
}
printf("%.8lf\n",1.0*sum/(2.0*n));
}
return 0;
}
