Description

Input Format

The first line of the input file contains seven numbers, namely $S_1, S_2, \dots, S_7$. The second line contains two numbers: the starting city $i$ and the destination city $j$. The third line contains a positive integer $c$, with $c \le 10000$, indicating that each of the following $c$ lines stores a pair of cities that are directly reachable from each other.

The information for a pair of directly reachable cities consists of three numbers: the indices of the two cities and the terrain type between these two cities. City indices are positive integers not exceeding $100$, but the indices are not necessarily continuous.

On the same line in the file, any two adjacent numbers are separated by a single whitespace character.

Output Format

Output a single line with the time required by the fastest route between the starting city $i$ and the destination city $j$.

0 1 0 0 0 0 0
1 4
4
1 2 1
1 3 1
2 4 2
3 4 3

5

Hint

Translated by ChatGPT 5