先生和遗书

题目背景

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