You are given a weighted directed graph of vertices and edges, with vertices numbered to and edges numbered to . The -th () edge connects from vertex to vertex (), and the weight of the edge is .
Also, triplets of integers are given. The -th () triplet is ().
You start at vertex and move to vertex by repeatedly moving along an edge.
In addition, for all (), if you move from vertex to vertex directly, we must next move to a vertex other than vertex .
Judge whether it is possible to reach vertex . If it is possible to reach, also calculate the minimum sum of the weights of the edges you pass through.
输入格式
The input satisfies the following constraints.
All inputs consist of integers.
输出格式
If you cannot reach vertex , output . Otherwise, output the minimum sum of the weights of the edges you pass through.
