#include<bits/stdc++.h>
//typedef long long ll;
// #define int long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rd read()
#define rd1 read1()
#define pos(i,a,b) for(int i=(a);i<=(b);i++)
#define neg(i,a,b) for(int i=(a);i>=(b);i--)
#define mp make_pair
#define ls (p<<1)
#define rs (p<<1|1)
#define zycisyourfather
using namespace std;

typedef pair<int,int> pii;

const int Max=4e3+10;
const int inf=0x3f3f3f;
const int M=1e9+7;
const int N=3;
const double eps=1e-7;
const double Pi=3.1415926535897;

inline int read()
{
    int x=0,k=1; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();}
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*k;
}
int n,m;
int head[Max],cnt;
int x[Max],y[Max],ans[Max];
bool vs[Max],vs1[Max],flag[Max];
struct Edge
{
    int to,nxt,l;
}e[Max];
struct Edge1
{
    int to,nxt;
}E[Max];
int hed[Max],cnt1;
struct Edge2
{
    int to,nxt;
}T[Max];
int tal[Max],cnt2;
void add1(int u,int v)
{
    E[++cnt1].to=v;
    E[cnt1].nxt=hed[u];
    hed[u]=cnt1;
}
void add2(int u,int v)
{
    T[++cnt2].to=v;
    T[cnt2].nxt=tal[u];
    tal[u]=cnt2;
}
void add(int u,int v,int w)
{
    e[++cnt].to=v;
    e[cnt].nxt=head[u];
    e[cnt].l=w;
    head[u]=cnt;
}
int num[Max],dis[Max];
bool vis[Max];
queue<int> q;

bool spfa(int s)
{
    mst(dis,inf);
    mst(vis,0);
    mst(num,0);
    while(!q.empty()) q.pop();
    dis[s]=0;
    vis[s]=1;
    num[s]=1;
    q.push(s);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        vis[x]=0;
        for(int i=head[x];i;i=e[i].nxt)
        {
            int now=e[i].to,len=e[i].l;
            if(dis[x]+len<dis[now])
            {
                dis[now]=len+dis[x];
                num[now]=num[x]+1;
                if(num[now]>n) return 1;//判断负环 
                if(!vis[now]) {vis[now]=1;q.push(now);}         
            }
        }
    }
    return 0;
}

void dfs1(int x)
{
    vs[x]=1;
    for(int i=hed[x];i;i=E[i].nxt)
    {
        int now=E[i].to;
        if(vs[now]) continue;
        dfs1(now);
    }
}

void dfs2(int x)
{

    vs1[x]=1;
    for(int i=tal[x];i;i=T[i].nxt)
    {
        int now=T[i].to;
        if(vs1[now]) continue;
        dfs2(now);
    }
}

int main()
{
    #ifdef zycisyourfather
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif 
    n=rd,m=rd;
    pos(i,1,m)
    {
        x[i]=rd,y[i]=rd;
        add1(x[i],y[i]);
        add2(y[i],x[i]);
    }
    dfs1(1);
    dfs2(n);
    if(!vs[n]) {puts("-1");return 0;}
    pos(i,1,n) 
    {
        if(vs[i]&&vs1[i]) flag[i]=1;
    }
    mst(ans,0);
    pos(i,1,m)
    {
        if(flag[x[i]]&&flag[y[i]]) 
        {
            add(x[i],y[i],9);
            add(y[i],x[i],-1);
        }
        else ans[i]=1;
    }
    //pos(i,1,n) add(0,i,0);这道题无所谓连不连通，不连通的自然不包括在1到n内，所以这部分随便赋值即可
    
    printf("%d %d\n",n,m);
    if(!spfa(1))
    {
        pos(i,1,m) 
        {
            if(ans[i]==0) 
            {
                ans[i]=dis[y[i]]-dis[x[i]];
            }
        }
        pos(i,1,m) printf("%d %d %d\n",x[i],y[i],ans[i]);
    }
    else puts("-1");
    return 0;
}