给定 nnn 个点 mmm 条带权边的有向图和 qqq 次询问，每次询问两个点之间的最短路。除了 n,m,qn,m,qn,m,q 外所有数据均随机。
1≤n≤2×105,1≤m≤3×106,1≤q≤104,1≤wi≤1091\le n\le 2\times 10^5,1\le m\le 3\times 10^6,1\le q\le 10^4,1\le w_i\le 10^91≤n≤2×105,1≤m≤3×106,1≤q≤104,1≤wi≤109。
时间限制为 10s10\text{s}10s。
（PKUSC2024 D2T3）
