本文共 1476 字，大约阅读时间需要 4 分钟。

#include
   
    using namespace std;const int maxn=1e5+1;int n,m,d[maxn],num[maxn],u[maxn],v[maxn],w[maxn],pre[maxn],sum=0;bool vis[maxn];vector
    
     
      >g[maxn];void spfa(int x){   	memset(vis,false,sizeof(vis));	for(int i=0;i<=n;++i) d[i]=0x3f3f3f3f;	d[x]=0;num[x]=0;	queue
      
       q;	q.push(x);	vis[x]=true;	while(!q.empty())	{   		int top=q.front();		q.pop();		vis[top]=false;		for(auto v:g[top])		{   			if(d[top]+1
       
        num[v.first]))			{   				d[v.first]=d[top]+1;				pre[v.first]=top;				num[v.first]=num[top]+v.second;				if(!vis[v.first]) q.push(v.first),vis[v.first]=true;			}		}	}}int main(){   	scanf("%d %d",&n,&m);	for(int i=1;i<=m;++i)	{   		scanf("%d %d %d",&u[i],&v[i],&w[i]);		g[u[i]].push_back({   v[i],w[i]});		g[v[i]].push_back({   u[i],w[i]});		sum+=w[i];	} 	spfa(1);	printf("%d\n",d[n]+sum-2*num[n]);	memset(vis,false,sizeof(vis));	int t=n;vis[1]=true;	while(t!=1) vis[t]=true,t=pre[t];	for(int i=1;i<=m;++i)	{   		if(w[i]&&(!vis[u[i]]||!vis[v[i]])) printf("%d %d 0\n",u[i],v[i]);//不在最短路径上的需要破坏的 		else if((pre[u[i]]==v[i]||pre[v[i]]==u[i])&&vis[u[i]]&&vis[v[i]]&&!w[i]) printf("%d %d 1\n",u[i],v[i]);//在最短路径上的需要修复的 	}}