破坏行动问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

恐怖组织伊阿德尔卡的首领拉本·灯打算摧毁一个敌对势力的石油运输系统。这个石油运输系统可以看成一个运输网络,由许多的结点和连接结点的管道构成。只有地点A生产石油,而生产的石油则通过管道输送到地点B,石油不能在中间结点累积。管道是双向的,每条管道连接两个不同的结点,而每两个结点间最多只有一条管道相连。每条管道有一个抗压指数,当石油的流量超过这个数管道就会爆炸。A地生产石油的速度可以认为是非常快的,但由于管道抗压指数的原因,能运到B的有一个上限。拉本·灯知道敌对势力采用了某种方案使得他们能输送最多的石油,但他不知道这个具体的方案是什么。拉本·灯有一种特殊的物质,可以让一条管道的抗压指数下降1。作为伊阿德尔卡首席恐怖程序员,你的任务就是告诉拉本·灯,让哪些管道的抗压指数下降,一定可以使管道爆炸从而摧毁运输网络。

Input

第1行包含四个整数n,m,s,t,表示有n个结点(编号为1,2,3,…,n),m条管道,s,t分别是A地和B地的编号。2<=n<=130,0<=m<=n(n-1)/2,1<=s,t<=n。
接下来m行每行描述一条管道,包含3个整数i,j,c。i和j分别为管道连接的2个结点,c为这条管道的抗压指数。1<=i,j<=n,1<=c<=10000。

Output

第1行输出抗压指数减少1就必定爆炸的管道条数k。
接下来k行每行输出一个整数p(1<=p<=m),说明第p条管道如果抗压指数减少1就必定爆炸。序号p按照管道输入的顺序,并按照p的升序输出。

Sample Input

4 4 1 4
2 4 100
1 2 1
3 1 100
4 3 1

Sample Output

2
2
4

Hint

 

Source