U45313.中心纪念碑

小明居住的城市有 $n$ 个街区，由若干条双向道路连接而成。其中，第 $i$ 个街区的人数为 $a_i$，第 $j$ 条道路的长度为 $b_j$。奇怪的是，从任意一个街区出发，无法实现不经过重复的一条道路就返回起点。

现在，市长决定要在一个街区建设城市中心纪念碑。但是这个计划面临的阻力很大，几乎每个街区都对此不满意，他们都想让纪念碑建设在他们的街区，至少不要太远。不过，每个街区对中心纪念碑的期望程度 $c$ 不同，$c_i$ 可表示为 ${p_i}^{p_i} mod 1314143$。

经过调查得知，如果中心纪念碑选址在街区 $u$，则第 $v$ 个街区的不满意度 $d_v=dis(u,v)×a_v×c_v$，其中 $dis(u,v)$ 表示从街区 $u$ 到街区 $v$ 的最短距离。

市长为了让他的口碑尽量好，决定选在一个满足让 $n$ 个街区的不满意度总和最小的街区建设纪念碑，换句话说，即在某街区建设纪念碑时 $\sum_{i=1}^{n} d_i$ 取值最小。

市长决定让他最信任的你来解决这个问题。

第一行，一个整数 $n$。

后 $n$ 行，每行 $2$ 个正整数，$a_i,p_i$，表示街区 $i$ 的信息

后若干行，每行 $3$ 个正整数，$u,v,b_i$，表示存在一条从街区 $u$ 到街区 $v$ 的路，长度为 $b_i$

两个用 分隔的正整数，分别表示最终选址和不满意度之和。若最终选址可能有多个，输出编号最小的街区。

测试点编号	$n$	$a_i$	$b_i$	$p_i$
$1$~$2$	$≤100$	$≤100$	$≤100$	$≤10$
$3$~$6$	$≤3000$	$≤300$	$≤300$	$≤5000$
$7$~$8$	$≤3000$	$≤300$	$≤300$	$≤2×10^5$
$9$~$12$	$≤10^5$	$≤300$	$≤300$	$≤5000$
$13$~$14$	$≤10^5$	$≤1000$	$≤1000$	$≤2×10^5$
$15$~$20$	$≤2×10^5$	$≤1000$	$≤1000$	$≤5×10^5$

对于 $100\%$ 的数据，$n≤2×10^5，a_i,b_i≤1000，p_i≤5×10^5$。

建议使用较快的输入输出，如果你认为你的算法时间/空间复杂度是正确的，请多交几遍，本题时间/空间的预留量是足够通过正常算法的。

数据已加强