ZS the Coder has drawn an undirected graph of n vertices numbered from 0 to n - 1 and m edges between them. Each edge of the graph is weighted, each weight is a positive integer.
The next day, ZS the Coder realized that some of the weights were erased! So he wants to reassign positive integer weight to each of the edges which weights were erased, so that the length of the shortest path between vertices s and t in the resulting graph is exactly L. Can you help him?
The first line contains five integers n, m, L, s, t (2 ≤ n ≤ 1000, 1 ≤ m ≤ 10 000, 1 ≤ L ≤ 109, 0 ≤ s, t ≤ n - 1, s ≠ t) — the number of vertices, number of edges, the desired length of shortest path, starting vertex and ending vertex respectively.
Then, m lines describing the edges of the graph follow. i-th of them contains three integers, ui, vi, wi(0 ≤ ui, vi ≤ n - 1, ui ≠ vi, 0 ≤ wi ≤ 109). ui and vi denote the endpoints of the edge and wi denotes its weight. If wi is equal to 0then the weight of the corresponding edge was erased.
It is guaranteed that there is at most one edge between any pair of vertices.
Print "NO" (without quotes) in the only line if it's not possible to assign the weights in a required way.
Otherwise, print "YES" in the first line. Next m lines should contain the edges of the resulting graph, with weights assigned to edges which weights were erased. i-th of them should contain three integers ui, vi and wi, denoting an edge between vertices ui and vi of weight wi. The edges of the new graph must coincide with the ones in the graph from the input. The weights that were not erased must remain unchanged whereas the new weights can be any positive integer not exceeding 1018.
The order of the edges in the output doesn't matter. The length of the shortest path between s and t must be equal to L.
If there are multiple solutions, print any of them.
5 5 13 0 4
0 1 5
2 1 2
3 2 3
1 4 0
4 3 4
YES
0 1 5
2 1 2
3 2 3
1 4 8
4 3 4
2 1 123456789 0 1
0 1 0
YES
0 1 123456789
2 1 999999999 1 0
0 1 1000000000
NO
Here's how the graph in the first sample case looks like :
In the first sample case, there is only one missing edge weight. Placing the weight of 8 gives a shortest path from 0 to 4 of length 13.
In the second sample case, there is only a single edge. Clearly, the only way is to replace the missing weight with 123456789.
In the last sample case, there is no weights to assign but the length of the shortest path doesn't match the required value, so the answer is "NO".
题意：给你n个点，和m条双向边，每条边的长度有它的长度（正整数），若此边的长度为0，则是要你修改此长度，改为成正整数，使得从出发点到终点，最短距离等于L，。若修改可以满足题意，输出所有边的信息。，若无法使得最短路距离为L，则输出NO。
思路：先不用那些边长为0的边 求出最短路，若此距离小于L，那么增大边长为0的边，也不会使得最短距离变大。此种情况输出NO； 若此距离等于L，那么直接输出这些边的信息，若边长为0，则输出1e18即可。
若此距离大于L，那么就要用上边长为0的边，使得最短路变小了；因为每条边为正整数，所以把那些边长为0的边全部变成1； 然后求出最短路，若大于L则输出NO，若等于L则输出YES，若小于L，用F数组记录最短路的路径，看这个最短路离L还差多少，让这条最短路径上任意一个可以改变的值（以前是0的边，可以标记一下）增加上这个差值。然后让这条路径以外的可变边全部变为1e18，使得只留下一条最短路径为L的路。
然后重新用最短路算法跑一边，找一下改变后的图的最短路还是不是L，若是L则输出YES，若小于L，说明刚才最短路增长后，最短路变成了另一条， 那么重复以上黑体字操作。 .......直到除了此条最短路为L以外，再没有其路能小于L的了，然后输出答案即可。
思路当天没想出来，结果晚上回去的路上，突然就想到了多次找最短路，补全L后，修改其他边为1e18。直到找到最短路为L为止。 用这个思路，代码一遍就过了。终于A掉了，美滋滋！！
代码：（因本人代码水平有限，写的挺长，代码用时：2000ms）
#include <iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<queue>
#include<map>
#include<algorithm>
#define inf 0x3f3f3f3f
#include <algorithm>
#define N 10005
#define LL long long
#define mem(a,b) memset(a,b,sizeof(a));
using namespace std;
LL ansu[N],ansv[N];
LL answ[N];//存边的信息
struct node
{
LL u,v,nex,id;
LL w,flag;
} e[400500];
LL head[N],f[N],vis[N];
LL cnt,S,T,n,m;
LL dis[N],L;
void add(LL u,LL v,LL w,LL id)
{
e[cnt].id=id;//哪条边
e[cnt].u=u;
e[cnt].v=v;
e[cnt].w=w;
if(w==0) e[cnt].flag=0;//标记，边长为0，标记为0
else e[cnt].flag=1;
e[cnt].nex=head[u];
head[u]=cnt++;
}
void init()
{
mem(head,-1);
cnt=0;
}
queue<LL>q;
map<LL,LL>ma;
void spfa(LL flag)
{
mem(f,-1);
mem(vis,0);
memset(dis,0x3f,sizeof dis);//初始化
dis[S]=0LL;//dis[i]表示i到出发点S的最短距离
vis[S]=1;//标记是否已经加入队列
while(!q.empty())
q.pop();
q.push(S);
while(!q.empty())
{
LL u=q.front();
q.pop();
for(LL i=head[u]; ~i; i=e[i].nex)
{
LL v=e[i].v;
LL w=e[i].w;
if(flag&&!w) continue;//flag为1的话，算最短路不带边长为0的边
if(dis[v]<=dis[u]+w) continue;
dis[v]=dis[u]+w;//更新v到S的最短距离
if(!flag) f[v]=i;//更新dis[v]后，更新f[v]，f[v]存u到v的这条路的编号i，通过这个来找到最短路路径。
if(vis[v]) continue;
vis[v]=1;
q.push(v);
}
vis[u]=0;
}
}
int main()
{
init();
scanf("%lld%lld%lld%lld%lld",&n,&m,&L,&S,&T);
for(LL i=0; i<m; i++)
{
scanf("%lld%lld%lld",&ansu[i],&ansv[i],&answ[i]);
add(ansu[i],ansv[i],answ[i],i);
add(ansv[i],ansu[i],answ[i],i);
}
spfa(1);
if(dis[T]<L)//计算出最短路（不带0的边），若太小，改变边长为0的边，也无法改变这条最短路的值。
{
printf("NO\n");
return 0;
}
else if(dis[T]==L)//找到答案
{
printf("YES\n");
for(LL i=0; i<m; i++)
printf("%lld %lld %lld\n",ansu[i],ansv[i],answ[i]==0LL?L+10:answ[i]);
return 0;
}
for(int i=0;i<cnt;i++)//让所有的边长为0的边变成1（正整数）中的最小值
if(!e[i].flag)
answ[e[i].id]=e[i].w=1;
while(1)
{
spfa(0);//求出最短路
if(dis[T]>L)
{
printf("NO\n");//第一次求出此值，这是整个图的最短路，因为边长为零的边一定至少是1，第一次就没有大于L，那么以后也不可能再大于L。
return 0;
}
else if(dis[T]==L)
{
printf("YES\n");
for(LL i=0; i<m; i++)
printf("%lld %lld %lld\n",ansu[i],ansv[i],answ[i]);
return 0;
}
else
{
LL u=T;
ma.clear();
LL sum=L-dis[T];
while(u!=S)
{
if(!e[f[u]].flag)
{
answ[e[f[u]].id]=e[f[u]].w=e[f[u]].w+sum;//将sum（差值）添加到第一个可修改边上。
sum=0;
ma[e[f[u]].id]=1;//标记此最短路上可修改的边的id
}
u=e[f[u]].u;//f[u]为找到上一个节点的编号。
}
for(int i=0;i<cnt;i++)//此条最短路以外的所有可修改的边全部修改成1e18,
if(!e[i].flag&&!ma[e[i].id])
answ[e[i].id]=e[i].w=L+10;
}
}
}