#include <bits/stdc++.h>
using namespace std;

const int MAXN = 4e3+10;
const int inf=0x3f3f3f3f;

int n,m;
vector <int> E1[MAXN],E2[MAXN];
vector <pair <int,int> > G[MAXN],E;
int dis[MAXN],vis[MAXN],cnt[MAXN];

void bfs(int s,vector <int> E[],bool F[]) {
    queue <int> Q;
    Q.push(s);
    F[s]=true;

    while(!Q.empty()) {
        int u=Q.front();
        Q.pop();
        for(int v : E[u]) 
            if(!F[v]) {
                F[v]=true;
                Q.push(v);
            }
    }
}

bool A[MAXN],B[MAXN];

bool spfa(int s) {
    for(int i=1;i<=n;i++) 
        dis[i]=inf,vis[i]=0;
    
    queue <int> Q;
    Q.push(s);
    dis[s]=0,vis[s]=1,cnt[s]++;
    
    while(!Q.empty()) {
        int u=Q.front();
        Q.pop();
        vis[u]=0;
        for(auto [v,val] : G[u]) 
            if(dis[v]>dis[u]+val) {
                dis[v]=dis[u]+val;
                if(!vis[v]) {
                    vis[v]=1;
                    Q.push(v);
                    cnt[v]++;
                    if(cnt[v]>n+1) return false;
                }
            }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n>>m;
    for(int i=1;i<=m;i++) {
        int u,v;
        cin>>u>>v;
        E.push_back({u,v});
        E1[u].push_back(v);
        E2[v].push_back(u);
    }

    bfs(1,E1,A);
    bfs(n,E2,B);

    if(!A[n]) {
        cout<<-1<<'\n';
        return 0;
    }
    
    for(auto [u,v] : E) {
        if(A[u] && B[v]) 
            G[u].push_back({v,9});
            G[v].push_back({u,-1});
    }
    
    if(!spfa(1)) cout<<-1<<'\n';
    else {
        cout<<n<<" "<<m<<'\n';
        for(auto [u,v] : E) {
            cout<<u<<" "<<v<<" ";
            if(A[u] && B[v]) cout<<dis[v]-dis[u]<<'\n';
            else cout<<1<<'\n';
        }
    }
    
    return 0;
}