#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
#define ll long long
#define f first
#define s second
#define PB push_back
#define MP make_pair
#define min(a, b) ((a < b)? a : b)
const int N = 1e5 + 5;
const int M = 1e9 + 7;
const long double INF = 1e14;
vector<vector<pair<int, int>>> adj(N);
bool vis[N]{false};
void init(int n){
for(int i = 0; i < n; i++) adj[i].clear();
memset(vis, false, sizeof(vis));
}
long double DFS(int v, int target, long double time, vector<int> arr){
// cout << v << ' ' << time << endl;
vis[v] = true;
if(v == target) return time;
// if(vis[v]) return INF;
long double mn = INF;
for(auto i : adj[v]){
if(vis[i.f]) continue;
long double temp;
if(arr[i.f] == 0){
temp = DFS(i.f, target, 0, arr);
}else if(arr[i.f] == 2){
temp = DFS(i.f, target, (long double)(time + i.s)/2, arr);
}else {
temp = DFS(i.f, target, time + i.s, arr);
}
mn = min(mn, temp);
// cout << mn << endl;
}
vis[v] = false;
return mn;
}
// Subtask 1~6 (Greedy)
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr){
init(n);
for(int i = 0; i < m; i++){
adj[x[i]].PB(MP(y[i], c[i]));
adj[y[i]].PB(MP(x[i], c[i]));
}
long double ans = DFS(0, h, 0, arr);
if(vis[h]){
return ans;
}else {
return -1;
}
}
// int main(){
// // Driver Code
// cout << solve(3, 2, 30, 2, {1, 2}, {2, 0}, {12, 4}, {1, 2, 1});
// cout << solve(4, 4, 30, 3, {0, 0, 1, 2}, {1, 2, 3, 3}, {5, 4, 2, 4}, {1, 0, 2, 1});
// }
