题意：

n个城市m条道路， 任务是在城市1和城市n之间选择一个最短路径，当有多个最短路径的时候选择影响值最小的（被摧毁的和修好的路的数目总数最少） ，道路分已修复和未修复两种状态，在选择好最短路径后，要修复好最短路径上未工作的路，并破坏其他路径上工作的路径。

题解：

修复 = 最短路的长度 - 最短路上修好的路
破坏的道路 = 整张图上修好的路 - 最短路径上修好的路
影响值= 修复+破化的道路
= 最短路上没修好的路+非最短路上修好的路
= 最短路的长度 - 最短路上修好的路 + 整张图上修好的路 - 最短路上修好的路
= 最短路的长度 + 整张图上修好的路 - 2 * 最短路上修好的路

所以要使影响值最小应该使得最短路径上面工作的道路最多
先spfa得到最短路
如果最短路相同，再判断路上修好的路的个数（在spfa的过程中记录）
根据公式得到影响值，影响值也就是题目要求输出的k
用pre实现路径存储，输出最短路上未修好的路
bool bo[]记录最短路径上哪些点出现过

代码：

代码内详细注释

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);
   return s*w;
}
int INF= 0x3f3f3f3f;
const int maxn=1e5+9;
struct node{
    int u,v,w;
}a[maxn];
//int vis[maxn];
int n,m;
int tot=0;//求路径中已修好的数量
pair<int,int>dis[maxn],pre[maxn];
bool vis[maxn],bo[maxn];
vector<pair<int,int> > edge[maxn];//存路径
queue<int>q;
void spfa()
{
    for(int i=1;i<=n;i++)dis[i]=make_pair(INF,0);
    dis[1].first=0;
    q.push(1);
    vis[1]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(pair<int,int> tmp:edge[u])
        {
            int v=tmp.first;
            int w=a[tmp.second].w;
            bool xx=((dis[v].first==dis[u].first+1)&&(dis[v].second<dis[u].second+w));
            //如果都是最短路，那就要已修好道路多的 
            if(dis[v].first>dis[u].first+1||xx)
            {
                dis[v].first=dis[u].first+1;
                dis[v].second=dis[u].second+w;
                pre[v]=make_pair(u,tmp.second);//存入上一个点以及编号
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v); 
                }
            }

        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a[i].u>>a[i].v>>a[i].w;
        edge[a[i].u].push_back(make_pair(a[i].v,i));//存下路径和序号 
        edge[a[i].v].push_back(make_pair(a[i].u,i));
        tot+=a[i].w;
    }
    spfa();
    int k;
    k=dis[n].first+tot-2*dis[n].second;
        //dis[n].first表示最短路的长度 
    // dis[n].second表示最短路上已修好的路 
    cout<<k<<endl;
    int now=n;
    while(now!=1)
    {
        int temp=pre[now].second;//上一个点的编号 
        if(a[temp].w==0)
        cout<<a[temp].u<<" "<<a[temp].v<<" "<<1<<endl;
        bo[temp]=1;//标记最短路上的路径 
        now=pre[now].first;
    }
    for(int i=1;i<=m;i++)
    {
        if(!bo[i]&&a[i].w==1)//如果不是最短路上的&&路是修好的
        cout<<a[i].u<<" "<<a[i].v<<" "<<0<<endl; 
    }
    return 0;
}