相遇

题目描述

喵星人和汪星人的世界是一个由 $n$ 个结点、$m$ 条边构成的无向图，边的边权代表边的长度。

喵星人站在编号为 $S$ 的结点上，汪星人站在编号为 $T$ 的结点上。

喵星人要从 $S$ 出发走向 $T$ 点，在喵星人动身的同时，汪星人也从 $T$ 出发走向 $S$ 点。

喵星人与汪星人知道自己不能在某个结点或者边上停下脚步，也知道自己只能沿从起点向终点的某一条最短路径以相同的速度前行。

命运，使两星人终将擦肩而过，使喵星人与汪星人既不会在一点相遇，也不会在边上邂逅。

现在，你想知道，喵星人与汪星人需要行走多久的距离，方能踏上对方曾伫立过的结点；你还想知道，在多少个不同的时间线中，喵星人与汪星人不会相遇。

两个时间线不同，当且仅当这两个时间线中喵星人与汪星人行走的路线不同。

输入格式

第一行四个整数 $n,m,S,T$，表示无向图的点数，边数以及两星人所站立的结点编号。

接下来 $m$ 行，每行三个整数 $x,y,z$，表示一条从 $x$ 到 $y$，边权为 $z$ 的无向边。

输出格式

第一行一个整数，表示喵星人与汪星人要走的最短路径的长度；

第二行一个整数，表示不同时间线的个数。

样例

样例输入

4 4 1 3
1 2 1
2 3 1
3 4 1
1 4 1

样例输出

2
2

数据范围

对于 $30\%$ 的数据，$1 \le n \le 10$，$1 \le m \le 30$；

对于另外 $30\%$ 的数据，保证从 $S$ 到 $T$ 的最短路径是唯一的。

对于 $100\%$ 的数据，$1 \le n \le 10^5$，$1 \le m \le 4\times 10^5$。

保证时间线的个数不超过 $10^9$。