Caution! This problem turned out to be NP-hard. But since there was no rules against writing a NP-hard problem, we decided to leave this problem here.
There is a bidirectional graph consisting of vertices and edges. The vertices and edges are numbered from 1 to and 1 to respectively, and the weight of edge is . () Given a natural number , find the length of the shortest simple path that starts from vertex 1 and ends at vertex , and consists of edges. A simple path is a path that does not visit same vertex twice, and length of a path is the sum of weight of edges that consists the path.
输入格式
In the first line, three space-separated integers , , are given.
In the next lines, three space-separated integers , , are given. They denote that edge is connecting vertex and vertex , and has weight .
No loops or multiple edges are given.
输出格式
Print the length of the shortest simple path that starts from vertex 1 and ends at vertex , and consists of edges. If there is no such path, print .
