背景

  萌萌哒tangjz帮了OI村一个大忙,不过他的探测器似乎太小了,还是有一些OIer群所在的孤岛游离在外。

  比如Bread和Lemon分别所在的两个OIer群就没有和大部队取得联系。。。 >_<

描述

  萌萌哒tangjz决定创造一些桥,使得某些孤岛能够连通,但是任意两个孤岛之间建的桥的尺寸可能不全一样,有的孤岛之间甚至不能创造桥。。。 >_<

  萌萌哒tangjz只能按照一定尺寸批量创造出一些桥,然后对一些桥进行尺寸修改。。。 T_T

  萌萌哒tangjz为了不麻烦,他选择的方案中,这些桥的尺寸的极差尽量最小,且在满足前面条件的情况下桥数量尽量小。

输入格式

  第一行五个整数N,M,K,S0和T0(其中M非负,其他为正数),表示孤岛个数(编号1~N),孤岛间已有的路径数量,孤岛间可以新增的桥的数量,Bread的OIer群所在孤岛编号和Lemon的OIer群所在孤岛编号。

  接下来M行,每行两个正整数Si和Ti,表示Si和Ti间已经有一条路径。(上次探测器探测到的并且修复的路径)

  接下来K行,每行三个正整数Xi,Yi和Li,表示第i个可加的桥连接Xi,Yi,尺寸为Li

输出格式

  如果无论如何Bread和Lemon都不能相见,仅输出-1,否则:

  第一行两个非负整数Abs和K‘,表示最小差值和需要增加的桥个数。

  接下来K‘行,升序输出桥的编号,每行一个正整数Number,表示需要增加的是第Number个桥。(本题设有Special Judge,您的答案不劣于标准输出即可得到该测试点的得分,不劣于是指您的极差不小于标准极差即可)

样例输入

3 0 3 1 3
1 2 10
1 2 5
2 3 8

样例输出

2 2
1
3

数据范围与约定

  • 均匀分布着40%的随机数据
  • 对于60%的数据:N\leq 500,M+K\leq 5000,L_{i}\leq 30000
  • 对于100%的数据:N\leq 1000,M+K\leq 20000,L_{i}\leq 10^{9}

来源

  其实这才是信心题?