背景

  在山的那边海的那边,是伟大而古老的OI大陆。

  __int64 ago,伟大的clj来到了这里,征服了gyz,从此OI大陆不再有征战,高度自治,OIer繁衍生息,整个大陆呈现和谐的景象。

  而如今,一位名叫Kinger Tangent的OIer探险家却无意中吸收了邪恶力量,从此性情大变。(似乎正在酝酿一个巨大的阴谋 >_<)

  Kinger Tangent醒来发现自己在一个不知名的山洞里,如果有人在场,一定能看到他的身上戾气若隐若现。一个念头在他的脑中挥散不去:"杀了他们!杀了阻碍我们的人!这世界是属于我们的!" Kinger Tangent一阵头痛,怒嚎几声,便失去了理智。他跑出山洞,似乎是跑向了OI村。

  萌萌哒男主Bread和女主Lemon住在OI村,他们相识于OI中学,二人一见如故,很快陷入了**的**。

  Kinger Tangent来到OI村,想起Bread经常在他面前晒妹,于是要把二人分隔两地,永世不能相见。

描述

  黑化的Kinger Tangent拥有了分裂大地的力量,他要分裂两人的家之间的一些路,使得Bread不能去找Lemon。(保证Bread家和Lemon家连通)

  从Bread家到Lemon家的路现在可以看成是一个有向图,具有N个点,M条边。(点的编号为1~N,边的编号按照离Kinger Tangent的距离由近到远依次为1~M)

  Kinger Tangent想要毁坏一条边的代价是Wi

  由于Kinger Tangent想要节省力量去毁坏更多和谐的事物,所以他的炸(?)路方案必定是总代价最小、边数量最小的,而且他希望能尽快做完这件事,所以他的炸(?)路对应编号必定是字典序最小的

输入格式

  第一行四个正整数N,M,S0,T0,分别表示点数,边数,Bread家的点编号,Lemon家的点编号。

  接下来N行,按照边的编号依次描述每条边,每行三个正整数Si,Ti,Wi,分别表示第i条边的起点、终点和毁坏代价。

输出格式

  第一行两个正整数W和K,表示总最小代价和最小炸(?)路数量。

  接下来K行,输出最小字典序方案,每行一个正整数Number,表示第Number条边要炸(?)毁。

样例输入

4 5 1 4
1 3 100
3 2 50
2 4 60
1 2 40
2 3 80

样例输出

60 1
3

数据范围与约定

  • 对于30%的数据:N\leq 10, M\leq 500
  • 对于60%的数据:N\leq 20, M\leq 1000
  • 对于100%的数据:N\leq 50,M\leq 5000,W_{i}\leq 10^{5}

来源

  神犇肯定做过,虽然数据加强了但是神犇必然AC。

  提醒:每点时限2s 请轻虐评测姬 >.<