rt，用的是 bfs + 拓扑排序，求调。

#include<bits/stdc++.h>

using namespace std;

int n,m;
int x,y,z;
int dis[100010];
bool vis[100010];
int f[100010];
int pre[100010];
int nxt[100010];
int in[100010];
int ans;

struct node{
	int to,w;
};

vector<node>v[100010],newv[100010];

queue<int>q;

void bfs(){
	q.push(1);
	dis[1]=0;
	vis[1]=1;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=0;i<v[x].size();i++){
			int to=v[x][i].to;
			if(vis[to]){
				if(dis[to]==dis[x]+1){
					newv[x].push_back(v[x][i]);
				}
				continue;
			}
			vis[to]=1;
			dis[to]=dis[x]+1;
			q.push(to);
			newv[x].push_back(v[x][i]);
			in[to]++;
		}
	}
}

void dfs(int x){
	if(pre[x]==0){
		//printf("%d ",x);
		return;
	}
	nxt[pre[x]]=x;
	dfs(pre[x]);
	//printf("%d ",x);
}

void dp(){
	q.push(1);
	f[1]=0;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=0;i<newv[x].size();i++){
			int to=newv[x][i].to;
			
			//printf("%d %d\n",f[x]+newv[x][i].w,f[to]);
			
			if(f[x]+newv[x][i].w>f[to]){
				//puts("qwq");
				f[to]=f[x]+newv[x][i].w;
				pre[to]=x;
			}
			in[to]--;
			if(!in[to]) q.push(to);
		}
	}
}

signed main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		f[i]=-1;
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z);
		v[x].push_back((node){y,z});
		v[y].push_back((node){x,z});
	}
	bfs();
	dp();
	
	//printf("qwq %d\n",f[n]);
	
	/*for(int x=1;x<=n;x++){
		for(int i=0;i<newv[x].size();i++){
			int to=newv[x][i].to;
			printf("%d ",to);
		}
		puts("");
	}
	*/
	
	dfs(n);
	
	for(int x=1;x<=n;x++){
		for(int i=0;i<v[x].size();i++){
			int to=v[x][i].to;
			if(to==nxt[x]){
				if(v[x][i].w==0){
					ans++;
				}
			}
			else if(v[x][i].w==1){
				if(x<to){
					ans++;
				}
			}
		}
	}
	
	printf("%d\n",ans);
	
	for(int x=1;x<=n;x++){
		for(int i=0;i<v[x].size();i++){
			int to=v[x][i].to;
			if(to==nxt[x]){
				if(v[x][i].w==0){
					printf("%d %d %d\n",x,to,1);
				}
			}
			else if(v[x][i].w==1){
				if(x<to){
					printf("%d %d %d\n",x,to,0);
				}
			}
		}
	}
	
	//for(int i=1;i<=n;i++) printf("%d ",pre[i]);
	return 0;
}