【题意】

            N<=10^5个城市，M<=10^5条边，保证无向联通并且没有自环和重边。边分成两种，一种是被毁坏的，用0表示，一种是没被毁坏的用1表示。现在要修1-n的最短路，并且使得这条路的影响值最小，一条道路的影响值定义为：最短路上的毁坏边数+不在最短路上的正常边数。输出影响值以及影响的边。

【解题方法】

           设几个变量来看一看，all代表所有的正常边,d代表最短路，最短路上的正常边为x。所以ans = d-x+all-x = all + d -2*x!

           观察一下上面这个等式会发现，除了x其他都是常量，所以要使得答案最小只需要使得x最大就可以啦。由于图上的权值最大1，所以bfs最短路就行了，在过程中维护f[i],g[i],pre[i]，分别代表最短路，最短路上的正常边，还有记录前驱。

【AC 代码】

#include <bits/stdc++.h>
using namespace std;
const int inf  = 0x3f3f3f3f;
const int maxn = 1e5+10;
const int maxm = 2e5+10;
int n,m,u,v,w,all,id,f[maxn],g[maxn],pre[maxn];
struct edge{
    int v,w,next;
}E[maxm];
int head[maxn],edge_cnt;
void init(){
    memset(head,-1,sizeof(head));
    edge_cnt=0;
}
void addedge(int u,int v,int w){
    E[edge_cnt].v=v,E[edge_cnt].w=w,E[edge_cnt].next=head[u],head[u]=edge_cnt++;
}
void bfs(){
    queue<int>que;
    for(int i=1; i<=n; i++) f[i]=inf;
    for(int i=1; i<=n; i++) g[i]=0;
    f[1]=g[1]=0;
    que.push(1);
    while(que.size()){
        int u=que.front();
        que.pop();
        for(int i=head[u]; ~i; i=E[i].next){
            int v=E[i].v,w=E[i].w;
            if(f[v]==inf){
                f[v]=f[u]+1;
                g[v]=g[u]+w;
                pre[v]=i;
                que.push(v);
            }else if(f[v]==f[u]+1){
                if(g[u]+w>g[v]){
                    g[v]=g[u]+w;
                    pre[v]=i;
                }
            }
        }
    }
}
int main()
{
    all=0;
    init();
    cin>>n>>m;
    for(int i=1; i<=m; i++){
        cin>>u>>v>>w;
        addedge(u,v,w);
        addedge(v,u,w);
        all+=w;
    }
    bfs();
    for(u=n; u!=1; u=E[id^1].v){
        id=pre[u];
        if(E[id].w==0){
            E[id].w=E[id^1].w=2;
        }else{
            E[id].w=E[id^1].w=0;
        }
    }
    cout<<f[n]+all-2*g[n]<<endl;
    //cout<<edge_cnt<<endl;
    for(int i=0; i<edge_cnt; i+=2){
        if(!E[i].w) continue;
        cout<<E[i^1].v<<" "<<E[i].v<<" "<<E[i].w-1<<endl;
    }
    return 0;
}