AT_birthday0410_d 先生と遺書

# 先生和遗书 ### 题目背景 JAPLJ：因为在Special Judge中发现了缺陷，所以进行修正。修正结束后立即进行重测！！！！！对不起！！我什么都会做的！！！！！！！！！ K从以前开始就喜欢精进这个词。 我解释说，这句话中也包含着禁欲的意思。 但后来我问了一下，它还含有比它更严重的含义，这让我很惊讶。 **为了道路应该牺牲一切，这是他的第一信条，所以摄欲和禁欲自不必说，即使是远离欲望的恋爱本身也会妨碍道路。** ——夏目漱石《心》 ------------ 我喜欢精进这个词，比什么都重要的道路...... 哇……，这是K短路啊。没错。这是什么……真让人吃惊啊。 ### 题面翻译 给出2个整数 $K,L$。在$50$个顶点以下的无重边自环的无向图中，求出连接某两点的路径中第 $K$ 短的路径，其长度恰好等于 $L$ 。 在路径中，可以通过同一条边两次以上，也可以访问同一个顶点两次以上。另外，也可以考虑不仅是最后，中途也会访问顶点一次以上的路径。这样的路径全部按照长度（通过边的权重的总和）升序排列。

一行两个整数 $ K , L $ 。

输出一个无向简单图，从顶点 $1$ 到顶点 $N$ 的第 $K$ 个最短路径的长度必须正好是 $L$ 。 第一行输出两个整数 $N,M$ ,表示输出的图有 $N$ 个顶点，$M$ 条边。 接下来 $M$ 行每一行输出三个正整数 $A_i ,B_i,C_i$，表示 $A_i ,B_i$ 间存在权重为 $C_i$ 的边。 如果这样的图不存在，输出 $-1$。

- $1 \le N \le 50 $， - $1 \le K \le 5000 $， - $1 \le L \le 10^9 $， - $1 \le A_i,B_i \le N，1 \le C \le 10^9 $。 - 输出的图无重边，自环。 除此之外原作者没有写明每个测试点的数据范围。 原作者：这个问题的输入数据分为“普通的情况”、“有点危险的情况”、“相当危险的情况”3种。不说明这3种具体是怎样的情况。对这个问题的分数如下决定。 - 如果“普通的情况”全部正确的话1分到手。 - 再加上“有点危险的情况”，如果全部正确的话，就更好了4分到手。 - 再加上“相当危险的情况”全部正确的话，就更不用说了200分全部到手。 ### 输入输出样例 #### 样例输入 #1 ``` 3 8 ``` #### 样例输出 #1 ``` 3 2 1 2 2 2 3 2 ``` #### 样例输入 #2 ``` 5000 1 ``` #### 样例输入 #2 ``` -1 ``` Translated by @xianggujiang