题目描述

一张有向无环图有 N 个点，编号为 0 ~ N-1。M 条边，可能有重边。

求：起点 S 到终点 T 的次短路长度及条数。点从 0 到 N-1 编号。输入数据保证有解。

输入

多组数据。

对于每组数据：

• 第一行： N, M, S, T
• 接下来 M 行，每行三个整数 u, v, w，表示从点 u 到点 v 有一条长度为 w 的有向边。

输出

每组数据的结果占一行，输出两个整数，依次表示 S 到 T 的次短路长度及条数。

样例输入

3 3 0 2
0 2 5
0 1 4
1 2 2

样例输出

6 1

数据范围

100% 的数据：$3\leqslant N\leqslant 50$，$1\leqslant M\leqslant 100$，$0\leqslant S, E < N$，$0 \leqslant u, v < N$，$0\leqslant w\leqslant 10^9$