SP21858 QTGIFT3 - Christmas is coming

圣诞节即将来临，DB 正准备为 TN 准备一份精美的礼物。 DB 和 TN 所在的城市拥有 $n$ 个交叉路口，每条连接两个路口之间的直接道路都有对应的长度。在圣诞夜，TN 会在第 $t$ 个交叉路口等待，而 DB 将从第 $s$ 个交叉路口出发，通过若干条道路到达约定地点。 为了不让 TN 等待太久，DB 希望选择一条最短路径。此外，他还想知道从 $s$ 到 $t$ 的不同最短路径的数量（确保至少存在一条可行路径）。 由于交叉路口和连接的数量太多，DB 无法自己完成计算，因此他需要你的帮助。

- 第一行包含三个正整数 $n, s, t$，分别表示城市中交叉路口的数量、起点 $s$ 和终点 $t$，满足 $2 < n \le 10^5$ 且 $s \neq t$。 - 接下来的 $n$ 行中，每行包含三个正整数 $l, r, w$，表示从第 $i$ 个位置到 $l$，$l+1$，...，$r$ 的每一条直接连接都具有长度 $w$，并满足 $1 \le l \le r \le n$ 和 $1 \le w \le 10^3$。

- 输出两个正整数，第一个是最短路径的长度，第二个是不同最短路径的数量，这一结果需要对 $10^{15}$ 取模。两个数之间用空格分隔。 **本翻译由 AI 自动生成**