FIRE Again

Time Limit: 4000 ms Memory Limit: 65536 KiB

Problem Description

  Now,there are n cities in the country,from city 0 to city n-1.And there are bidirectional roads which connect these city,and each road has its lenth.And furthermore there will be more than one road from one city to another!It is true that there will be one way to any city from any another one.And in every city it has some firemen.Now you are the chief of these firemen in the s city.Unfortunatly,some day a fire breaks out in the t city.So,you must reach there as soon as possible.But you want to know how many shortest way from s city to t city.And in the way you can call the fireman in the city you through to help you.This time you have enough people work for you, so you can call all the firemen in all the shortest path to help.

Input

  The first line of the input is the number t,,the number of the test case.
Then for each test case:
the first line is two numbers:n(2 ≤ n ≤ 1000),the number of the cities,m(1 ≤ m < 100000),the number of the roads.
the next line is n numbers,the number of the firemen in each city.
the next m lines,each line these are there three numbers x,y,w.x,y are the two cities the road connect.and w is the lenth of the road. at last is two number s,t,(0 ≤ s,t < n,s ≠ t).

Output

  for each test case output two numbers,the number of the shortest way from s city to t city and the number of the firemen you can call in all the shortest path.

Sample Input

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

Sample Output

2 4

Hint

 

Source

2009湖南大学校赛