Problem: BubbleSquare social network is celebrating 13^{th} anniversary and it is rewarding its members with special edition BubbleSquare tokens. Every member receives one personal token. Also, two additional tokens are awarded to each member for every friend they have on the network. Yet, there is a twist – everyone should end up with different number of tokens from all their friends. Each member may return one received token. Also, each two friends may agree to each return one or two tokens they have obtained on behalf of their friendship.

Input

First line of input contains two integer numbers n and k (2 ≤ n ≤ 12500, 1 ≤ k ≤ 1000000) - number of members in network and number of friendships.

Next k lines contain two integer numbers a_i and b_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i) - meaning members a_i and b_i are friends.

Output

First line of output should specify the number of members who are keeping their personal token.

The second line should contain space separated list of members who are keeping their personal token.

Each of the following k lines should contain three space separated numbers, representing friend pairs and number of tokens each of them gets on behalf of their friendship.

Examples

Input


2 1
1 2


Output


1
1 
1 2 0


Input


3 3
1 2
1 3
2 3


Output


0
1 2 0
2 3 1
1 3 2

Note

In the first test case, only the first member will keep its personal token and no tokens will be awarded for friendship between the first and the second member.

In the second test case, none of the members will keep their personal token. The first member will receive two tokens (for friendship with the third member), the second member will receive one token (for friendship with the third member) and the third member will receive three tokens (for friendships with the first and the second member).

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast")
using namespace std;
namespace Base {
inline char gc(void) {
  static char buf[100000], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
template <class T>
inline void read(T &x) {
  T flag = (T)1;
  x = 0;
  static char ch = gc();
  for (; ch > '9' || ch < '0'; ch = gc()) flag = ch == '-' ? -1 : 1;
  for (; ch >= '0' && ch <= '9'; ch = gc()) x = (x << 1) + (x << 3) + (ch & 15);
  x *= flag;
  return;
}
inline void readstr(string &x) {
  x = "";
  static char ch;
  while (isspace(ch = gc()))
    ;
  while (x += ch, !isspace(ch = gc()))
    ;
}
inline void readstr(char *s) {
  do *s = gc();
  while ((*s == ' ') || (*s == '\n') || (*s == '\r'));
  do *(++s) = gc();
  while ((~*s) && (*s != ' ') && (*s != '\n') && (*s != '\r'));
  *s = 0;
  return;
}
inline void printstr(string x, int num = 0, char ch = '\n') {
  for (int i = num; i < x.size(); ++i) putchar(x[i]);
  putchar(ch);
}
inline void readch(char &x) {
  while (isspace(x = gc()))
    ;
}
char pf[100000], *o1 = pf, *o2 = pf + 100000;
template <class T>
inline void println(T x, char c = '\n') {
  if (x < 0)
    (o1 == o2 ? fwrite(pf, 1, 100000, stdout), *(o1 = pf)++ = 45 : *o1++ = 45),
        x = -x;
  static char s[15], *b;
  b = s;
  if (!x) *b++ = 48;
  for (; x; *b++ = x % 10 + 48, x /= 10)
    ;
  for (; b-- != s; (o1 == o2          ? fwrite(pf, 1, 100000, stdout),
                    *(o1 = pf)++ = *b : *o1++ = *b))
    ;
  (o1 == o2 ? fwrite(pf, 1, 100000, stdout), *(o1 = pf)++ = c : *o1++ = c);
}
int wbuf[25], _wl = 0;
template <class T>
inline void write(T x) {
  if (x == 0) {
    putchar(48);
    return;
  }
  if (x < 0) putchar('-'), x = -x;
  _wl = 0;
  while (x) wbuf[++_wl] = x % 10, x /= 10;
  for (int i = _wl; i >= 1; i--) putchar(wbuf[i] + 48);
}
template <class T>
inline void writeln(T x) {
  write(x);
  puts("");
}
template <class T>
inline void writeln(T x, char c) {
  write(x);
  putchar(c);
}
template <class T>
inline void writeln(char c, T x) {
  putchar(c);
  write(x);
}
template <class T>
inline void chkmax(T &x, const T y) {
  x > y ? x = x : x = y;
}
template <class T>
inline void chkmin(T &x, const T y) {
  x < y ? x = x : x = y;
}
template <class T>
inline T max(const T &x, const T &y, const T &z) {
  return x > y ? (x > z ? x : z) : (y > z ? y : z);
}
inline void file(string str) {
  freopen((str + ".in").c_str(), "r", stdin);
  freopen((str + ".out").c_str(), "w", stdout);
}
struct Vector {
  double x, y;
  Vector(double _x = 0, double _y = 0) : x(_x), y(_y) {}
  inline Vector Vary(void) { return Vector(x, -y); }
  inline bool operator<(const Vector &rhs) const {
    return x == rhs.x ? y < rhs.y : x < rhs.x;
  }
  inline Vector operator-(const Vector &rhs) const {
    return Vector(x - rhs.x, y - rhs.y);
  }
  inline Vector operator+(const Vector &rhs) const {
    return Vector(x + rhs.x, y + rhs.y);
  }
  inline Vector operator*(const double &rhs) const {
    return Vector(x * rhs, y * rhs);
  }
  inline Vector operator/(const double &rhs) const {
    return Vector(x / rhs, y / rhs);
  }
  inline Vector operator*(const Vector &rhs) const {
    return Vector(x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x);
  }
};
}  // namespace Base
using namespace Base;
const int N = 1e6 + 100;
int x[N], y[N], w[N], s[N], v[N];
bool in[N * 2];
vector<pair<int, int> > e[N];
vector<int> res;
int n, m;
int main() {
  read(n);
  read(m);
  for (register int i = (1); i <= (m); i++) {
    read(x[i]);
    read(y[i]);
    w[i] = 1;
    s[x[i]]++;
    s[y[i]]++;
    e[max(x[i], y[i])].push_back(make_pair(min(x[i], y[i]), i));
  }
  for (register int i = (1); i <= (n); i++) {
    for (register int it = (0); it <= (int(e[i].size()) - 1); it++) {
      if (!v[e[i][it].first]) {
        v[e[i][it].first] = 1;
        w[e[i][it].second] = 0;
        s[i]--;
      }
      in[s[e[i][it].first]] = 1;
    }
    for (register int it = (0); it <= (int(e[i].size()) - 1); it++) {
      if (!in[s[i]]) break;
      s[i]++;
      v[e[i][it].first] = 0;
      w[e[i][it].second]++;
    }
    for (register int it = (0); it <= (int(e[i].size()) - 1); it++)
      in[s[e[i][it].first]] = 0;
  }
  for (register int i = (1); i <= (n); i++)
    if (v[i]) res.push_back(i);
  writeln(int(res.size()));
  for (register int it = (0); it <= (int(res.size()) - 1); it++)
    writeln(res[it], ' ');
  puts("");
  for (register int i = (1); i <= (m); i++) {
    writeln(x[i], ' ');
    writeln(y[i], ' ');
    writeln(w[i]);
  }
  return 0;
}