#include "cyberland.h"
#include "bits/stdc++.h"
#define ff first
#define ss second
#define pp pop_back
#define ll long long
#define pb push_back
#define ls(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define wr cout << "------------------------" << endl
using namespace std;
const int N = 1e5 + 5;
vector<pair<int, int>> g[N];
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
for(int i = 0;i<M;++i){
g[x[i]].pb({c[i], y[i]});
g[y[i]].pb({c[i], x[i]});
}
priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> pq;
const int INF = 1e9 + 7;
vector<vector<int>> dp(N, vector<int>(K + 1, INF));
pq.push({0, 0, 0});
dp[0][0] = 0;
while(!pq.empty()){
auto [cost, x, k] = pq.top(); pq.pop();
if(dp[x][k] != cost or x == H) continue;
for(auto [val, y]:g[x]){
if(arr[x] == 2){
int req1 = cost + val;
int req2 = cost + val >> 1;
if(dp[y][k] > req1){
dp[y][k] = req1;
pq.push({req1, y, k});
}
if(k + 1 <= K and dp[y][k + 1] > req2){
dp[y][k + 1] = req2;
pq.push({req1, y, k + 1});
}
}
else if(!arr[x]){
int req = val;
if(dp[y][k] > req){
dp[y][k] = req;
pq.push({req, y, k});
}
}
else{
int req = cost + val;
if(dp[y][k] > req){
dp[y][k] = req;
pq.push({req, y, k});
}
}
}
}
// wr;
int ans = INF;
// for(int j = 0;j<N;++j){
// for(int i = 0;i<=4;++i) {
// cout << dp[j][i] << ' ';
// }
// cout << endl;
// }
for(int i = 0;i<=K;++i) ans = min(ans, dp[H][i]);
for(int i = 0;i<N;++i){
g[i].clear();
}
return ans;
}
/*
1
3 2 30
2
1 2 1
1 2 12
2 0 4
1
4 4 30
3
1 0 2 1
0 1 5
0 2 4
1 3 2
2 3 4
*/
