以下の条件を満たす辺の集合 \(S\) を常に管理します。

• その辺は、今あなたがいる可能性のある頂点といる可能性のない頂点を結んでいる

そして、\(i\) 日目の旅では以下のことをします。

• \(S\) の中で、通行時間 \(X_i\) 以下の辺がある限り、そのようなものを \(1\) つ \(S\) から取り出して \(a\) とし、以下を行う
  
  • \(a\) の端点のうちあなたがいる可能性がなかった方を \(x\) とする
  • \(x\) を「あなたがいる可能性のある頂点」としてマークし、隣接する辺を見て、必要なら \(S\) に新たに追加する

\(S\) を保持するデータ構造としてC++ における priority_queue などを使って、通行時間の短い順に取得・削除するとよいです。
処理の過程で「あなたがいる可能性のある頂点」としてマークしたときに、既に \(S\) に入っている辺が \(S\) の条件を満たさなくなることがありますが、辺が \(S\) から取り出された時に「\(S\) の要素としての条件を満たさないならば無視する」という処理を入れれば問題ありません。
各頂点高々 \(1\) 回しか新たに「あなたがいる可能性のある頂点」としてマークされないので、\(S\) に辺が追加される回数は \(O(M)\) 回となります。
よって、全体で \(O(N + M \log(M) + Q)\) で解くことができます。