use std::{cmp::Reverse, collections::BinaryHeap}; #[allow(non_snake_case)] use proconio::input; use proconio::marker::Usize1; const INF: i64 = 1_000_000_000_000_000_000; fn main() { input! { N: usize, M: usize, P: usize, Y: i64, roads: [(Usize1, Usize1, i64); M], shops: [(Usize1, i64); P], } let mut graph = vec![vec![]; N]; for &(u, v, w) in &roads { graph[u].push((v, w)); graph[v].push((u, w)); } let mut dist = vec![INF; N]; dist[0] = 0; let mut pq = BinaryHeap::<(Reverse, usize)>::new(); pq.push((Reverse(0), 0)); while let Some((Reverse(d), u)) = pq.pop() { if dist[u] < d { continue; } for &(v, w) in &graph[u] { if dist[v] > d + w { dist[v] = d + w; pq.push((Reverse(d + w), v)); } } } let mut ans = 0; for &(d, e) in &shops { let money = 0.max(Y - dist[d]); ans = ans.max(money / e); } println!("{ans}"); }