#include<bits/stdc++.h>
using namespace std;
int k,s,t,ans=2147482646,n,m;
bool vis[40000];
struct bian{
	int u;
	int v;
	int w;
}a[40040];    //储存每一条边
void dfs(int k,int hp,int v){    //第一个参数为魔力值 第二个为当前血量 第三个为当前点
	if(hp>=ans) return;          //超出当前的答案直接退出
	if(v==s){       //到达终点
		ans = min(ans,hp);
		return;
	}
	for(int i = 1;i<=m;i++){
		int pur = a[i].u==v ? a[i].v : a[i].u;    //找到移动后的点
		if((a[i].u==v || a[i].v==v) && vis[pur]==false){    //找到与当前点相连且未访问的点
			vis[pur]=true;
			dfs(k+1,hp+a[i].w/k,pur);    //深搜
			vis[pur]=false;
		}
	}
}
int main(){
	cin>>n>>m>>s>>t;
	for(int i = 1;i<=m;i++){
		scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
	}
	vis[t] == true;
	dfs(1,0,t);
	cout<<ans;
	return 0;
}

我的思路是从终点开始深搜，每前进一个点就标记并加上对应的hp和魔力值