#include <bits/stdc++.h>   using namespace std;   const int M = 100010;   int n, m;   struct road {     int to, th;     bool f;   } in;   struct dot {     int come_road;     int come_point;     bool func;   } r[M];   vector<road> work[M];   vector<road> not_work[M];   vector<road> rw[M];   vector<road> rnw[M];   bool vis[M];   int d[M];   int broken_road[M];   bool inq[M];   int tot, u;   int input() {     int ans = 0;     char ch;     while (1) {       ch = getchar();       if (ch ==     || ch ==   n ) return ans;       ans *= 10;       ans += ch -  0 ;     }     return ans;   }   void output(int out) {     if (out == 0) {       putchar( 0 );       return;     }     char ans[10];     int cnt = 0;     while (out) {       ans[cnt++] = out % 10 +  0 ;       out /= 10;     }     for (int i = cnt - 1; i >= 0; i--) putchar(ans[i]);   }   int main() {     while (~scanf( %d%d , &n, &m)) {       tot = 0;       memset(broken_road, 0x3f, sizeof(broken_road));       memset(vis, 0, sizeof(vis));       memset(d, 0x3f, sizeof(d));       for (int i = 1; i <= n; i++) {         work[i].clear();         not_work[i].clear();         rw[i].clear();         rnw[i].clear();       }       int x, y, fun;       getchar();       for (int i = 0; i < m; i++) {         x = input();         y = input();         fun = input();         in.to = y;         in.th = i;         if (!fun) {           in.f = 0;           not_work[x].push_back(in);           in.to = x;           rnw[y].push_back(in);         } else {           tot++;           in.f = 1;           work[x].push_back(in);           in.to = x;           rw[y].push_back(in);         }       }       memset(inq, 0, sizeof(inq));       inq[1] = 1;       d[1] = 0;       queue<int> q;       q.push(1);       broken_road[1] = 0;       while (!q.empty()) {         u = q.front();         q.pop();         inq[u] = 0;         int v;         for (int i = 0; i < work[u].size(); i++) {           v = work[u][i].to;           if (d[u] + 1 < d[v] ||               (d[u] + 1 == d[v] && broken_road[u] < broken_road[v])) {             d[v] = d[u] + 1;             r[v].come_point = u;             r[v].come_road = work[u][i].th;             r[v].func = 1;             broken_road[v] = broken_road[u];             if (!inq[v]) {               q.push(v);               inq[v] = 1;             }           }         }         for (int i = 0; i < rw[u].size(); i++) {           v = rw[u][i].to;           if (d[u] + 1 < d[v] ||               (d[u] + 1 == d[v] && broken_road[u] < broken_road[v])) {             d[v] = d[u] + 1;             r[v].come_point = u;             r[v].come_road = rw[u][i].th;             r[v].func = 1;             broken_road[v] = broken_road[u];             if (!inq[v]) {               q.push(v);               inq[v] = 1;             }           }         }         for (int i = 0; i < not_work[u].size(); i++) {           v = not_work[u][i].to;           if (d[u] + 1 < d[v] ||               (d[u] + 1 == d[v] && broken_road[u] + 1 < broken_road[v])) {             d[v] = d[u] + 1;             r[v].come_point = u;             r[v].come_road = not_work[u][i].th;             r[v].func = 0;             broken_road[v] = broken_road[u] + 1;             if (!inq[v]) {               q.push(v);               inq[v] = 1;             }           }         }         for (int i = 0; i < rnw[u].size(); i++) {           v = rnw[u][i].to;           if (d[u] + 1 < d[v] ||               (d[u] + 1 == d[v] && broken_road[u] + 1 < broken_road[v])) {             d[v] = d[u] + 1;             r[v].come_point = u;             r[v].come_road = rnw[u][i].th;             r[v].func = 0;             broken_road[v] = broken_road[u] + 1;             if (!inq[v]) {               q.push(v);               inq[v] = 1;             }           }         }       }       int p = n;       while (p != 1) {         vis[r[p].come_road] = 1;         if (r[p].func)           tot--;         else           tot++;         p = r[p].come_point;       }       output(tot);       puts(  );       for (int i = 1; i <= n; i++) {         for (int j = 0; j < work[i].size(); j++) {           if (!vis[work[i][j].th]) {             output(i);             putchar(   );             output(work[i][j].to);             putchar(   );             puts( 0 );           }         }         for (int j = 0; j < not_work[i].size(); j++) {           if (vis[not_work[i][j].th]) {             output(i);             putchar(   );             output(not_work[i][j].to);             putchar(   );             puts( 1 );           }         }       }     }     return 0;   }   