큰 트럭

큰 트럭을 몰고 도시의 한 지점에서 다른 지점으로 물건을 옮긴다. 지도에는 지점과 지점을 잇는 도로의 길이가 적혀 있다. 사장은 출발지에서 도착지까지 최단 경로로만 가라고 지시했고, 도착하면 주행 거리계를 확인한다. 그래서 이동 거리의 합은 최단 거리와 정확히 같아야 한다.

친구들은 트럭에 빈자리가 많다는 것을 알고, 여러 지점에 들러 물건을 실어 달라고 부탁했다. 어떤 지점을 지나가면 그 지점에 있는 물건을 모두 싣는다. 트럭이 커서 실을 수 있는 물건 수에는 제한이 없다. 부탁받은 물건을 전부 싣지는 못하더라도, 이동 거리가 최단 거리보다 길어지지 않는 선에서 최대한 많이 싣고 싶다.

위 그림은 도시의 예시 두 개다. 정점은 지점, 간선은 도로, 정점 안의 점은 친구가 부탁한 물건이다. 왼쪽 그림에서는 1번 지점에서 6번 지점까지 가야 한다. 1 → 2 → 3 → 6으로 가면 이동 거리는 9이고 물건 4개를 싣는다. 1 → 4 → 5 → 6도 이동 거리가 9지만 물건을 하나 더 싣는다. 1 → 4 → 3 → 6은 물건을 더 많이 싣지만 이동 거리가 최단 거리보다 길어지므로 갈 수 없다.

첫째 줄에 지점의 개수 $n$이 주어진다 ($2 \le n \le 100$). 지점에는 1번부터 $n$번까지 번호가 붙어 있고, 1번이 출발지, $n$번이 도착지다.

둘째 줄에 $n$개의 정수 $t_1, t_2, \dots, t_n$이 공백으로 구분되어 주어진다. $t_i$는 $i$번 지점에서 실어야 하는 물건의 개수다 ($0 \le t_i \le 100$).

셋째 줄에 도로의 개수 $m$이 주어진다. $m$은 0 이상 $n(n-1)/2$ 이하다.

다음 $m$개 줄에는 도로가 한 줄에 하나씩, 세 정수 $a$, $b$, $d$로 주어진다. $a$번 지점과 $b$번 지점을 잇는 길이 $d$의 도로가 있다는 뜻이다 ($1 \le a, b \le n$, $1 \le d \le 100$). 모든 도로는 양방향으로 지날 수 있다. 두 지점을 잇는 도로는 많아야 하나이고, 한 지점에서 그 지점으로 돌아오는 도로는 없다.

1번 지점에서 $n$번 지점으로 갈 수 없으면 impossible을 출력한다.

갈 수 있으면 한 줄에 두 정수를 공백으로 구분해 출력한다. 첫 번째 수는 1번 지점에서 $n$번 지점까지 최단 경로의 길이이고, 두 번째 수는 길이가 그 최단 거리와 같은 경로 중에서 실을 수 있는 물건의 최대 개수다. 출발지와 도착지에 있는 물건도 개수에 넣는다.