Cable Car

#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
typedef long long int ll;
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    vector<pair<ll,int> > adj[n+1];
    for(int i=0;i<m;i++){
        int u,v;
        ll w;
        scanf("%d %d %lld",&u,&v,&w);
        adj[u].push_back({w,v});
        adj[v].push_back({w,u});
    }
    ll dist[n+1];for(int i=0;i<=n;i++)dist[i] = -2e18;
    int sour,dest;
    ll people;
    scanf("%d %d %lld",&sour,&dest,&people);

    dist[sour] = 0;
    priority_queue<pair<pair<ll,int> ,int > >pq;
    pq.push({{0,sour},0});
    bool visited[n+1];for(int i=0;i<=n;i++)visited[i] = false;

    int parent[n + 1];
    while(!pq.empty()){
        int u = pq.top().first.second;
        int prev = pq.top().second;
        pq.pop();
        if(visited[u])continue;
        visited[u] = true;
    //  printf("%d -> %d\n",prev,u);
        parent[u] = prev;
        for(int i=0;i<adj[u].size();i++){
            ll w = adj[u][i].first;
            int v = adj[u][i].second;
            if(!visited[v] && w > dist[v]){
                dist[v] = w;
                pq.push({{dist[v],v},u});
            }
        }
    }
    int pr = dest;
    ll minw = 2e9;
    do{
        if(dist[pr] < minw)minw = dist[pr];
        pr = parent[pr];
    }while(pr != sour);

    printf("%lld",(people + minw - 2)/(minw - 1));
    return 0;
}