#include<bits/stdc++.h>
using namespace std;
#define pi pair<int,int>
const int maxn=5005;
int n,m,dis[maxn],cnt[maxn],vis[maxn];
int sd[maxn],ed[maxn];
vector<int> v1[maxn];
vector<pi> v[maxn];
int p1[maxn],p2[maxn];
struct node
{
  int x,y;
}a[maxn];
void check1(int x)
{
  queue<int> q;
  p1[x]=1;q.push(1);
  while(!q.empty())
  {
    int p=q.front();q.pop();
    for(int i=0;i<v1[p].size();i++)
    {
      int y=v1[p][i];
      if(!p1[y])
      {
        p1[y]=true;
        q.push(y);
      }
    }
  }
}
void check2(int x)
{
  queue<int> q;
  p2[x]=1;q.push(x);
  while(!q.empty())
  {
    int p=q.front();q.pop();
    for(int i=0;i<v1[p].size();i++)
    {
      int y=v1[p][i];
      if(!p2[y])
      {
        p2[y]=true;
        q.push(y);
      }
    }
  }
}
bool relax(int x,int y,int w)
{
  if(dis[x]+w<dis[y])
  {
    dis[y]=dis[x]+w;
    return true;
  }
  return false;
}
bool check()
{
  memset(dis,0x3f,sizeof(dis));
  queue<int> q;
  q.push(0);dis[0]=0;
  vis[0]=1;
  while(q.size())
  {
    int x=q.front();
    q.pop();
    // if(vis[x]) continue;
    if(cnt[x]>=n) return false;
    vis[x]=0,cnt[x]++;
    for(int i=0;i<v[x].size();i++)
    {
      int y=v[x][i].first,w=v[x][i].second;
      if(relax(x,y,w))
      {
        if(!vis[y])
				{q.push(y);vis[y]=1;}
      }
    }
  }
  return true;
}
int main()
{
  scanf("%d %d",&n,&m);
  for(int i=1;i<=m;i++)
  {
    int x,y;
    scanf("%d %d",&x,&y);
    a[i].x=x,a[i].y=y;
    v1[x].push_back(y);
    v1[y].push_back(x);
  }
  check1(1);check2(n);
  for(int i=1;i<=m;i++)
  {
    int x=a[i].x,y=a[i].y;
    if(!p1[x]||!p2[y]) continue;
    v[x].push_back({y,9});
    v[y].push_back({x,-1});
  }
  for(int i=1;i<=n;i++)
    v[0].push_back({i,0});
  if(!p1[n]||!check())
  {
    puts("-1");
    return 0;
  }
  printf("%d %d\n",n,m);
  for(int i=1;i<=m;i++)
  {
    int x=a[i].x,y=a[i].y;
    if(!p1[x]||!p2[y])
      printf("%d %d %d\n",x,y,1);
    else
      printf("%d %d %d\n",x,y,abs(dis[y]-dis[x]));
  }
  return 0;
}