AT_pakencamp_2021_day3_h パ研王国と貨物輸送

一个王国有 $N$ 座城市和 $M$ 条双向道路。城市的编号从 $1$ 到 $N$。第 $i$ 条道路连接 $u_i$ 市和 $v_i$ 市，长度为 $l_i$。 有 $K$ 项运输任务，第 $i$ 项任务是将货物用车从 $s_i$ 市运到 $g_i$ 市。如果该任务能在时刻 $T$ 之前完成，将会获得 $m_i$ 元的利润。 由于道路狭窄，在同一时刻，同一道路中的同一处（不包含端点）不能有多辆车。 请安排一种运输方案，最大化总利润。

第一行输入四个整数 $N,M,K,T$。 接下来 $M$ 行，第 $i$ 行输入三个整数 $u_i,v_i,l_i$。 接下来 $K$ 行，第 $i$ 行输入三个整数 $s_i,g_i,m_i$。

第一行输出一个整数 $P$，你选择的任务数量（$0\le P\le K$）。 接下来 $P$ 行，第 $i$ 行中首先输出三个整数 $x,t,k$，分别表示你选择的第 $i$ 项任务的编号，开始时间和经过道路条数。你需要保证任意两个 $x$ 都不同。然后输出 $k+1$ 个整数 $a_0,a_1,...,a_k$，依次表示经过的城市编号（$a_0$ 为 $s_x$，$a_k$ 为 $g_x$，$a$ 中各元素互不相同）。

#### 评分 测试点共有 $20$ 个，均按[该生成代码](https://img.atcoder.jp/pakencamp-2021-day3/bf6dee05788c2762cbe1d62d26cac87a.zip)随机生成。如果你的输出不合法，则本题得分为 $0$。若你的全部输出均合法，则计算你 $20$ 个测试点中的利润合计总额并记为 $S$，将你的得分定为 $\min(800,\lfloor\frac{10000}{S}\rfloor)$ 的值。 #### 数据规模与约定 输入输出示例仅做说明用，并不满足约束条件。 对于 $100\%$ 的测试点，数据保证： - $N=100$，$M=200$，$K=500$，$T=10000$； - $1\le u_i\lt v_i\le N$，$1\le l_i\le 100$，$(u_i,v_i)\neq (u_j,v_j)$； - $1\le s_i,t_i\le N$，$s_i\neq t_i$，$1\le m_i\le 1000$； - 输入给出的无向图连通。