30pts求条，WA on #20,#29

#include<bits/stdc++.h>
using namespace std;
const int N=2e4+10;
int n,m;
int a[N],b[N],c;
int op;
int dis[N];
bool vis[N],f,pd;
int hed[N],nxt[N],vtx[N],cost[N];
int cnt[N];
int tot;
inline void addedge(int x,int y,int z){
	vtx[++tot]=y;
	cost[tot]=z;
	nxt[tot]=hed[x];
	hed[x]=tot;
}
inline void SPFA(int s){
	queue<int>q;
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof vis);
	q.push(s);vis[s]=1,dis[s]=0;
	while(!q.empty()&&!f){
		int x=q.front();q.pop();
		for(int i=hed[x];i&&!f;i=nxt[i]){
			if(dis[vtx[i]]>dis[x]+cost[i]){
				if(dis[vtx[i]]<0&&cnt[vtx[i]]>=n)f=1;
				dis[vtx[i]]=dis[x]+cost[i];
				if(vtx[i]<=n&&x<=n)cnt[vtx[i]]=cnt[x]+1;
				if(!vis[vtx[i]])q.push(vtx[i]);
				vis[vtx[i]]=1;
			}
		}
	}
}
inline void bfs(int s){
	queue<int>q;
	q.push(s);
	while(!q.empty()){
		int x=q.front();q.pop();
		vis[x]=1;
		for(int i=hed[x];i;i=nxt[i]){
			if(!vis[vtx[i]])q.push(vtx[i]);
			vis[vtx[i]]=1;
		}
	}
}
int main(){
	cin>>n>>m;
//	cout<<n<<' '<<m<<'\n';
	for(int i=1;i<=m;i++){
		cin>>a[i]>>b[i];
//		cout<<a<<' '<<b<<' '<<1<<'\n';
		addedge(a[i],b[i],9);
		addedge(b[i],a[i],-1);
	}
	bfs(1);
//	for(int i=1;i<=n;i++)cout<<vis[i]<<' ';
//	puts("");
	if(!vis[n]){
		puts("-1");
		return 0;
	}
	for(int i=1;i<=n;i++)addedge(0,i,0);
	SPFA(0);
	if(f||dis[n]==0x3f3f3f3f)puts("-1");
	else{
		cout<<n<<' '<<m<<'\n';
		for(int i=1;i<=m;i++){
			cout<<a[i]<<' '<<b[i]<<' '<<max(1,min(9,dis[b[i]]-dis[a[i]]))<<'\n';
		}
	}
	return 0;
}