问题描述

每年，Jill都会在两个村庄之间进行一次自行车旅行。这两个村庄之间有若干条不同的路线可供选择，但Jill对旅行距离有上限要求。给定一张包含村庄和道路（及其距离）的地图，你需要编写一个程序，列出所有满足Jill距离要求的路线，并按距离从短到长排序。

假设条件

1. 任意两个村庄之间最多有一条双向道路，且距离为正整数。
2. 没有道路从一个村庄直接返回其自身（即无自环）。
3. Jill只关心单程旅行，不考虑返程。
4. 旅行过程中，Jill不会重复访问任何村庄。
5. 最大旅行距离不超过$9999$单位。

输入格式

输入包含多个测试用例，每个用例包含以下数据（由空格或换行分隔）：

1. $NV$：地图中的村庄数量（不超过$20$个）。
2. $NR$：道路数量。
3. $NR$个三元组，每个三元组表示一条道路：$C1\ C2\ DIST$（$C1$和$C2$是村庄编号，$DIST$是道路距离）。
4. $SV$和$DV$：起点和终点村庄编号（村庄编号为$1$到$NV$）。
5. $MAXDIST$：Jill能接受的最大单程距离。

最后一个测试用例后跟一个$-1$表示输入结束。

输出格式

对于每个测试用例：

1. 第一行输出用例编号（如Case 1:）。
2. 随后每行输出一条可行路线，格式为距离: 路径（路径按村庄编号顺序排列，用空格分隔）。
3. 路线按距离从短到长排序；距离相同时，按字典序升序排列。
4. 若无可行路线，输出NO ACCEPTABLE TOURS。
5. 两个测试用例的输出之间用空行分隔。

示例输入与输出

输入示例：

4 5
1 2 2
1 3 3
1 4 1
2 3 2
3 4 4
1 3
4

4 5
1 2 2
1 3 3
1 4 1
2 3 2
3 4 4
1 4
10

5 7
1 2 2
1 4 5
2 3 1
2 4 2
2 5 3
3 4 3
3 5 2
1 3
8

-1

输出示例：

Case 1:
 3: 1 3 
 4: 1 2 3 

Case 2:
 1: 1 4 
 7: 1 3 4 
 8: 1 2 3 4 

Case 3:
 3: 1 2 3 
 7: 1 2 4 3 
 7: 1 2 5 3 
 8: 1 4 2 3 
 8: 1 4 3 

数据来源

Pacific Northwest 2004