题目描述

$W$ 市的交通系统由 $n$ 个站点和 $m$ 条单向道路组成，小威有一张可以乘坐 $k$ 公里的单次票，在每个站点可以指定走任意一条可使用的单向道路（从一条单向道路的一端到另一端为一站地）。

为了物尽其用，小威想知道，从哪些站出发再到哪些站结束可以存在刚好长度为 $k$ 公里的路径，请按字典序从小到大输出。

输入格式

第一行输入 $n,m$。

接下来 $m$ 行，每行输入三个整数 $u,v,w$，表示有一条从 $u$ 到 $v$ 长度为 $w$ 公里的单向路径，允许重边自环。

最后一行输入 $k$。

对于所有数据，满足：$1 \le n \le 100, 1 \le w \le 10,1 \le m \le 10^6, 0 \le k \le 2 \times 10^9 $。

输出格式

每一行输出一个长度为 $k$ 的路径的起点和终点 $(u, v)$，按字典序输出，不重复。

3 3
1 2 1
2 3 1
3 1 1
2

1 3
2 1
3 2