1866. [国家集训队2011]星际探险

众所周知，新世纪的科学很发达，于是Ray 和DarkRaven 开始了星
际探险，他们在宇宙中开辟了一片空间，建造了N 个空间站。这N 个空
间站由一些单向的时空隧道连接，这些时空隧道都有一个穿越指数，穿过
这些时空隧道，你可以走到未来或者回到过去，当然，这些都是由穿越指
数决定的。
有一天，Ray 和DarkRaven 开始了一场比赛。他们要从一个空间站S
出发去另一个空间站T，先到的人获胜。DarkRaven 一定会选一条能最快
到达T 的路线。他希望Ray 输给他，所以事先在Ray 的飞船上设定了飞
行路径，使得Ray 从S 到T 只能走一条特定的路径。但是，Ray 有对策，
他有一台能够操纵时空隧道的机器，这台机器每次可以把某一条时空隧道
的穿越指数增加或减少1，但是因为操纵机器很累，所以Ray 希望尽可能
少改动，当然，如果改动后从某个空间站经过一系列的穿越可以在从这个
空间站出发之前回到这个空间站，那么这样的改动是不允许的。修改之后，
DarkRaven 依然会走能最快到达终点的路线，所以Ray 是不可能赢的。但
他请你帮助他确定改动时空隧道的方案，使得他能和DarkRaven 同时到达
T。

输入的第一行包含两个整数N 和M，代表空间站的数目和时空隧道
的数目。N <= 10000; M <= 100000。
接下来M 行，每行三个整数u、v 和w，代表从空间站u 到空间站
v 有一条时空隧道，它的穿越指数是w。0 <= w <= 2000。空间站的编号
是0 ... N - 1。
第M + 2 行包含一个整数p，代表DarkRaven 在Ray 的飞船上设定
的那条路径的空间站数。第M + 3 行包含p 个数，那条路径上的空间站的
编号，第一个数是S，最后一个数是T。

输出的第一行包含一个整数，表示Ray 走那条路径并且能够赢得比赛
的情况下操纵时间机器的最小次数。
接来来输出M 行，其中第i 行输出一个整数w，表示把输入中第i 条
时空隧道的穿越指数增加w， w 可以是负数。
4
如果第一问（操纵时间机器的最小次数）正确，可以得到该测试点
20% 的分数，如果在此基础上方案可行，能得到该测试点100% 的分数。