The input contains multiple test cases.
The first line of each case is an integer N (2<=N<=600), representing the number of cities in the country.
The second line contains one integer M (0<=M<=10000), which is the number of roads.
The following M lines are the information of the roads. Each line contains three integers A, B and T, which means the road between city A and city B will cost time T. T is in the range of [1,500].
Next part contains N integers, which are either 1 or 2. The i-th integer shows the supporting leader of city i.
To simplify the problem, we assume that Mr. M starts from city 1 and his target is city 2. City 1 always supports leader 1 while city 2 is at the same side of leader 2.
Note that all roads are bidirectional and may have multiple edges.
Input is ended with a case of N=0.
翻译：输入包含多个测试用例。
每个案例的第一行是一个整数N（2<=N<=600），表示该国城市的数量。
第二行包含一个整数M（0<=M<=10000），表示道路的数量。
接下来的M行是道路信息。每行包含三个整数A、B和T，表示A城市和B城市之间的道路需要花费时间T。T的范围为[1,500]。
接下来包含N个整数，这些整数要么是1，要么是2。第i个整数表示城市i的辅助领导者。
为了简化问题，我们假设M先生从城市1出发，他的目标是城市2。城市1始终支持领导者1，而城市2则与领导者2站在同一边。
请注意，所有道路都是双向的，且可能有多条边。
输入以N=0的情况结束。