HZNUOJ

FIRE Again

Tags:
Time Limit:  4 s      Memory Limit:   64 MB
Submission:0     AC:0     Score:100.00

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.

Samples

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
output
2 4

Source

湖南大学2009校赛