学校准备在校园里设置一条推荐步行路线。从起点 $s$ 走到终点 $t$，每条道路都有长度，每个地点还有一个“风景值”。

现在你需要找到一条满足以下规则的路线：

1. 总长度最短；
2. 如果最短路线不止一条，选择风景值总和最大的路线；
3. 如果仍不唯一，选择整条路径字典序最小的路线（按经过结点编号序列比较）。

其中，路径风景值总和包含起点和终点的风景值。

输入格式

第一行输入四个整数：

n m s t

表示地点数、道路数、起点编号、终点编号。

第二行输入 $n(2 \leq n \leq 200)$ 个整数，第 $i$ 个整数表示编号为 $i$ 的地点的风景值。

接下来 $m(1 \leq m \leq 5000)$ 行，每行输入三个整数：

u v w

表示地点 $u$ 与地点 $v$ 之间有一条双向道路，长度为 $w(1 \leq w \leq 10^6)$。

保证 s 能到达 t。

输出格式

输出共两行。

第一行输出两个整数：

dist beauty

表示所选路线的总长度和风景值总和。

第二行输出整条路径上的结点编号，结点之间用一个空格分隔。

样例输入

5 6 1 5
3 2 5 4 6
1 2 2
2 5 2
1 3 2
3 5 2
1 4 1
4 5 3

样例输出

4 14
1 3 5

样例说明

从 1 到 5 的最短距离为 4。满足最短距离的路线有多条，其中 1-3-5 的风景值总和最大，为 3+5+6=14。