#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int n,m,x[N],y[N],f[N],dis[N];
bool p[N],vis[N],v[N][N];
vector<int> g[N];
vector<pair<int,int> > g2[N];
queue<int> q;
bool SPFA(){
	memset(vis,false,sizeof(vis));
	memset(dis,0x3f,sizeof(dis));
	vis[0]=true,dis[0]=0;
	q.push(0);
	while(!q.empty()){
		int x=q.front(); q.pop();
		vis[x]=false;
		for(int i=0;i<g2[x].size();i++){
			int y=g2[x][i].first,z=g2[x][i].second;
			if(dis[y]>dis[x]+z){
				dis[y]=dis[x]+z;
				f[y]=f[x]+1;
				if(f[y]>n) return false;
				if(!vis[y]){
					vis[y]=true;
					q.push(y);
				}
			}
		}
	}
	return true;
}
bool dfs(int x){
	if(x==n||p[x]) return true;
	for(int i=0;i<g[x].size();i++){
		int y=g[x][i];
		if(v[x][i]) continue;
		v[x][i]=true;
		if(dfs(y)){
			g2[x].push_back({y,9});
			g2[y].push_back({x,-1});
			p[x]=true;
		}
	}
	return p[x];
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x[i],&y[i]);
		g[x[i]].push_back(y[i]);
	}
	for(int i=1;i<=n;i++)
		g2[0].push_back({i,0});
	if(!dfs(1)||!SPFA()){
		puts("-1");
		return 0;
	}
	printf("%d %d\n",n,m);
	for(int i=1;i<=m;i++){
		printf("%d %d ",x[i],y[i]);
		int k=abs(dis[x[i]]-dis[y[i]]);
		if(k>=1&&k<=9) printf("%d\n",k);
		else puts("1");
	}
	return 0;
}