1274. [AHOI2009] 最小截断

【题目描述】

宇宙旅行总是出现一些意想不到的问题，这次小可可所驾驶的宇宙飞船所停的空间站发生了故障，这个宇宙空间站非常大，它由N个子站组成，子站之间有M条单向通道，假设其中第i（1＜＝i＜＝M）条单向通道连接了xi，yi两个中转站，那么xi子站可以通过这个通道到达yi子站，如果截断这条通道，需要代价ci。现在为了将故障的代价控制到最小，小可可必须想出一个截断方案，使a站不能到达b子站，并且截断的代价之和最小。我们称之为最小截断，小可可很快解决了这个故障，但是爱思考的小可可并不局限于此，为了今后更方便的解决同类故障，他考虑对每条单向通道：

1，是否存在一个最小代价路径截断方案，其中该通道被切断？

2，是否对任何一个最小代价路径切断方案，都有该通道被切断？

聪明的你能帮小可可解决他的疑问吗？

【输入格式】

第一行有4个整数，依次为N，M，a和b；

第二行到第(m+1)行每行3个正整数x，y，c表示x子站到y子站之间有单向通道相连，单向通道的起点是x终点是y，切断它的代价是c（1＜＝c＜＝10000）；

两个子站之间可能有多条通道直接连接。

【输出格式】

对每一个单向通道，按输入的顺序，依次输出一行包含两个非0即1的整数，分别表示对问题一和问题二的回答（其中1表示是，0表示否）。每行两个整数之间用一个空格分隔开。

【样例输入】

   6 7 1 6 
   1 2 3
   1 3 2
   2 4 4 
   2 5 1
   3 5 5 
   4 6 2
   5 6 3

【样例输出】

1 0
1 0
0 0
1 0
0 0
1 0
1 0

【提示】

提示：100％的数据中，N＜＝4000，M＜＝60000

  70％的数据中，N＜＝1000，M＜＝40000

  40％的数据中，N＜＝200，M＜＝2000

【来源】

AHOI2009