Migrated from Lutece 42 滑雪与时间胶囊

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

a180285非常喜欢滑雪。他来到一座雪山，这里分布着$M$条供滑行的轨道和$N$个轨道之间的交点（同时也是景点），而且每个景点都有一编号$i$($1\leq i\leq N$)和一高度$H_i$。a180285能从景点$i$滑到景点$j$当且仅当存在一条$i$和$j$之间的边，且$i$的高度不小于$j$。

与其他滑雪爱好者不同，a180285喜欢用最短的滑行路径去访问尽量多的景点。如果仅仅访问一条路径上的景点,他会觉得数量太少。于是a180285拿出了他随身携带的时间胶囊。这是一种很神奇的药物，吃下之后可以立即回到上个经过的景点（不用移动也不被认为是a180285滑行的距离）。

请注意，这种神奇的药物是可以连续食用的，即能够回到较长时间之前到过的景点（比如上上个经过的景点和上上上个经过的景点）。

现在，a180285站在$1$号景点望着山下的目标，心潮澎湃。他十分想知道在不考虑时间胶囊消耗的情况下， 以最短滑行距离滑到尽量多的景点的方案（即满足经过景点数最大的前提下使得滑行总距离最小）。

你能帮他求出最短距离和景点数吗？

Input

输入的第一行是两个整数$N$,$M$。

接下来$1$行有$N$个整数$H_i$，分别表示每个景点的高度。

接下来$M$行，表示各个景点之间轨道分布的情况。每行$3$个整数$U_i$,$V_i$,$K_i$。表示编号为$U_i$的景点和编号为$V_i$的景点之间有一条长度为$K_i$的轨道。

$1\leq N\leq 2000$

$1\leq M\leq 1000000$,$1\leq H_i\leq 1000000000$,$1\leq K_i\leq 1000000000$。

Output

输出一行，表示a180285最多能到达多少个景点，以及此时最短的滑行距离总和。

Samples

3 3
3 2 1
1 2 1
2 3 1
1 3 10

3 2

Resources

SCOI2012