求调

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+5;
int n,m,tot,head[N<<1],dis[N],vis[N],cnt[N],usf[N],ok[N];
vector<int> G[N],D[N];
struct edge {
	int ne,u,v,w;
} e[N<<1],rem[N];
void add(int u,int v,int w) {
	e[++tot]= {head[u],u,v,w};
	head[u]=tot;
}
int spfa(int s) {
	for(int i=1; i<=n; i++) {
		dis[i]=INT_MAX;
		vis[i]=0;
	}
	queue<int> q;
	q.push(s);
	vis[s]=1;
	dis[s]=0;
	while(!q.empty()) {
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=e[i].ne) {
			int v=e[i].v,w=e[i].w;
			if(dis[v]>dis[u]+w) {
				dis[v]=dis[u]+w;
				if(!vis[v]) {
					vis[v]=1;
					q.push(v);
					if(++cnt[v]>=n+1) return 1;
				}
			}
		}
	}
	return 0;
}
void bfs1(int s) {
	queue<int> q;
	q.push(s);
	ok[s]=1;
	while(!q.empty()) {
		int u=q.front();
		q.pop();
		for(auto v : G[u]) {
			q.push(v);
			ok[v]=1;
		}
	}
}
void bfs2(int s) {
	queue<int> q;
	q.push(s);
	usf[s]=ok[s];
	while(!q.empty()) {
		int u=q.front();
		q.pop();
		for(auto v : D[u]) {
			q.push(v);
			usf[v]=ok[v];
		}
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++) {
		cin>>rem[i].u>>rem[i].v;
		G[rem[i].u].push_back(rem[i].v);
		D[rem[i].v].push_back(rem[i].u);
	}
	bfs1(1);
	bfs2(n);
	for(int i=1;i<=m;i++) {
		if(usf[rem[i].u]&&usf[rem[i].v]) {
			add(rem[i].v,rem[i].u,-1);
			add(rem[i].u,rem[i].v,9);
		}
	}
	if(spfa(1)) {
		cout<<"-1"<<endl;
		return 0;
	}
	if(dis[n]==INT_MAX) {
		cout<<"-1"<<endl;
		return 0;
	}
	cout<<n<<' '<<m<<endl;
	for(int i=1;i<=m;i++) {
		cout<<rem[i].u<<' '<<rem[i].v<<' ';
		if(!usf[rem[i].u]||!usf[rem[i].v]) cout<<"1"<<endl;
		else cout<<dis[rem[i].v]-dis[rem[i].u]<<endl;
	}
	return 0;

}