入力

入力は以下の形式で標準入力から与えられる。

N M K T
u_1 v_1 l_1
u_2 v_2 l_2
\hspace{0.8cm}\vdots
u_M v_M l_M
s_1 g_1 m_1
s_2 g_2 m_2
\hspace{0.8cm}\vdots
s_K g_K m_K

制約

• N=100
• M=200
• K=500
• T=10000
• 1 \leq u_i \lt v_i \leq N
• 1 \leq l_i \leq 100
• (u_i,v_i) \neq (u_j,v_j)
• 1 \leq s_i,t_i \leq N
• s_i \neq t_i
• 1 \leq m_i \leq 1000
• 入力はすべて整数である
• どの都市からどの都市へも、いくつかの道路を経由して移動することができる。

出力

あなたの輸送計画の内容を、以下の形式に従って出力せよ。

P
\text{data}_1
\text{data}_2
\hspace{0.3cm}\vdots
\text{data}_P

まず、P はあなたの輸送計画において行われる仕事の数である。この値は 0 以上 K 以下である必要がある。

そして、その後に出力される \text{data}_i はあなたの輸送計画において行われる仕事のうち、i 個目のものについての情報を表す。この情報は、以下の形式で出力される必要がある。

x t k
a_0 a_1 \ldots a_k

まず、x は \text{data}_i において行われる仕事が仕事 x であることを表す。\text{data}_1 における x、\text{data}_2 における x、\cdots、\text{data}_P における x は互いに異なる必要がある。

次に、t は仕事 x を開始する時刻が t であることを表す。この値は 0 以上 T 以下である必要があり、また t から始めて経由する都市を順に訪れていったとき、最後の頂点に到着する時刻が T より真に遅くなってはならない。

そして最後に、k および数列 a=(a_0,a_1,\ldots,a_k) は、経由する都市の列を表す。a の各要素は互いに異なる必要があることに注意せよ。

テストケースの生成方法

テストケースは全部で 20 個あり、それらは制約を満たす範囲内でほぼランダムに生成されています。

具体的には、こちらの生成コードによって生成されています。

採点

20 個のテストケースのうちのいずれかで問題文中の条件（同じ時刻に同じ道路内の同じ地点に複数の車が存在してはいけない）に反する出力、ないし不正な出力がなされた場合、あなたの提出は不正解となり、得られる得点は 0 となる。

そうでなく、あなたが 20 個のテストケースすべてにおいて正当な出力をした場合、あなたの得点は 20 個のテストケースすべてにおける利益の合計を S として、\min(800,\frac{S}{10000}) の小数点以下切り上げとなる。