这题k=5。。。
所以直接dfs下去，每次spfa跑出一条最短路，然后枚举哪条边被删，然后dfs下一层就行了
由于随机数据，所以每一层的最短路不会很长，spfa也可能比dijstra快，所以复杂度不会达到50^5这个上限
#include<bits/stdc++.h>
using namespace std;const int maxl=60;
const int inf=2e9+10;int n,k,ans;
int frm[maxl],dis[maxl];
int f[maxl][maxl];
bool con[maxl][maxl];
bool in[maxl];inline void prework()
{scanf("%d%d",&n,&k);int u,v,w;for(int i=1;i<=n*(n-1)/2;i++){scanf("%d%d%d",&u,&v,&w);f[u][v]=f[v][u]=w;con[u][v]=con[v][u]=true;}
}inline void spfa()
{queue<int> q;for(int i=2;i<=n;i++)dis[i]=inf;dis[1]=0;in[1]=true;q.push(1);int u,v;while(!q.empty()){u=q.front();q.pop();for(v=1;v<=n;v++)if(con[u][v] && dis[v]>dis[u]+f[u][v]){dis[v]=dis[u]+f[u][v];frm[v]=u;if(!in[v])in[v]=true,q.push(v);}in[u]=false;}}inline void dfs(int now)
{if(now>k){spfa();ans=max(ans,dis[n]);return;}spfa();int u=n,len=0;vector<int> a;a.push_back(n);len=1;while(u!=1){u=frm[u];++len;a.push_back(u);}for(int i=0;i<len-1;i++){con[a[i]][a[i+1]]=con[a[i+1]][a[i]]=false;dfs(now+1);con[a[i]][a[i+1]]=con[a[i+1]][a[i]]=true;}
}inline void mainwork()
{ans=0;dfs(1);
}inline void print()
{printf("%d\n",ans);
}int main()
{int t;scanf("%d",&t);for(int i=1;i<=t;i++){prework();mainwork();print();}return 0;
}