给定一张N个点M条边的有向无环图，每条边都有一个长度。给定一个起点S和一个终点T。若从S到T的路径都经过某条边，则称这条边是有向图的必经边或桥。 PKU ACM队要从S点到T点。他们在路上可以搭乘两次车。每次可以从任意位置（甚至是一条边上的任意位置）上车，从任意位置下车，但连续乘坐的长度不能超过q米。除去这两次乘车外，剩下的路段步行。定义从S到T的路径的危险程度等于步行经过的桥上路段的长度之和。求从S到T的最小危险程度是多少。

第一行包含整数 L，表示共有 L 组测试数据。

每组测试数据，第一行包含五个整数 N, M, S, T, q。

接下来 M 行，每行包含三个整数 u, v, w，表示点 u 到点 v 存在一条边，长度为 w。

每组数据输出一个结果，每个结果占一行。

若没有从 S 到 T 的路径，则输出 -1。

• 1 \le L \le 5
• 1 \le N \le 10^5
• 1 \le M \le 2 \times 10^5
• 0 \le S, T < N，S \neq T
• 1 \le q \le 10^9
• 1 \le w \le 1000