free

?#include<bits/stdc++.h>
using namespace std;
int n,m,S,T,K;
int A[3003][3005];
#define INF 100000099
int dp[3003][3005];
#define P pair<int,int>
priority_queue<P,vector<P>,greater<P> >pq;
void dijk()
{
    for(int i=1; i<=n; i++)
    {

        for(int j=0; j<=K; j++)
        {
            dp[i][j]=INF;
            if(i==S)dp[i][j]=0;
        }
        //cout<<i<<" "<<dp[S][0]<<endl;
        
        //if(i==0)cout<<dp[S][i]<<endl;
    }
    //cout<<dp[S][1]<<endl;
    pq.push(P(0,S));
    while(!pq.empty())
    {
        P a=pq.top();
        pq.pop();
        int x=a.first;
        int y=a.second;
        //if(y==T)
        // cout<<y<<endl;
        if(dp[y][0]<x)continue;
        // dp[y][0]=x;///???
        // cout<<y<<" "<<dp[y][0]<<endl;
        for(int i=1; i<=n; i++)
        {
            //cout<<dp[i][0]<<" "<<dp[y][0]<<" "<<A[y][i]<<" NM"<<i<<endl;
            //cout<<(A[y][i]!=0)<<(A[y][i]!=INF)<<(dp[i][0]<dp[y][0]+A[y][i])<<endl;
            if((A[y][i]!=0)&&(A[y][i]!=INF)&&(dp[i][0]>dp[y][0]+A[y][i]))
            {
                // cout<<i<<"???"<<endl;
                dp[i][0]=min(dp[i][0],dp[y][0]+A[y][i]);
                for(int j=1; j<=K; j++)
                    dp[i][j]=min(dp[i][j],min(dp[y][j]+A[i][j],dp[y][j-1]));
                //cout<<"TRE"<<endl;
                pq.push(P(dp[i][0],i));
            }
        }
    }

}
int main()
{
    scanf("%d%d%d%d%d",&n,&m,&S,&T,&K);
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(i!=j)A[i][j]=INF;
        }
    }
    int a,b,c;
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        A[a][b]=A[b][a]=c;
    }
    int ans=INF;
    dijk();
    for(int i=0; i<=K; i++)
    {
        ans=min(ans,dp[T][i]);
        // cout<<dp[T][i]<<endl;
    }
   
    cout<<ans<<‘\n‘;

}