题目

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+1;
struct sb{
	int v,t,nxt; 
}e[N];
struct ssb{
	int x,y,z;
}a[N];
int n,m,h[N],vis[N],f[N],d[N],prt[N],cnt=0,ans;
queue<int>q;
void add(int x,int y,int z){
	e[++cnt].v=y,e[cnt].t=z,e[cnt].nxt=h[x],h[x]=cnt;
}
void dsb(int s){//SPFA
    memset(f,0x3f,sizeof f); 
    memset(d,0x3f,sizeof d);
	q.push(s);d[s]=0;f[s]=0;
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=h[u];i;i=e[i].nxt){
			int v=e[i].v,t=e[i].t;
			if(f[v]>f[u]+1)f[v]=f[u]+1,d[v]=d[u]+(t^1),prt[v]=(i+1)/2,q.push(v);
			else if(f[v]==f[u]+1&&d[v]>d[u]+(t^1))d[v]=d[u]+(t^1),prt[v]=(i+1)/2;
		}
	}
}
void az(int u,int st){
	if(u==1)return;
	vis[prt[u]]=1;
	az(a[prt[u]].x==u?a[prt[u]].y:a[prt[u]].x,st);
	if(!st)return;
	if(!a[prt[u]].z)cout<<a[prt[u]].x<<' '<<a[prt[u]].y<<' '<<1<<'\n';
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i].x>>a[i].y>>a[i].z;add(a[i].x,a[i].y,a[i].z);add(a[i].y,a[i].x,a[i].z);
	}dsb(1);
	ans=d[n];
	az(n,0);
	for(int i=1;i<=n;i++)if(!vis[i]&&a[i].z)ans++;
	cout<<ans<<'\n';az(n,1);
	for(int i=1;i<=m;i++)if(!vis[i]&&a[i].z)cout<<a[i].x<<' '<<a[i].y<<' '<<0<<'\n';
    return 0;
}