#include <bits/stdc++.h>   using namespace std;   const double pi = acos(-1.0);   const int inf = (int)1e9;   struct vert {     int to, z, num;   };   struct ans {     int x, y, z;   };   const int N = (int)(1e5) + 5;   int n, m;   vector<vert> g[N];   vector<int> d(N, inf);   vector<int> dp(N, inf);   vector<int> pr(N, -1);   vector<bool> road(N);   void go() {     queue<int> q;     q.push(0);     d[0] = 0;     while (!q.empty()) {       int v = q.front();       q.pop();       for (int i = 0; i < (int)g[v].size(); ++i) {         int to = g[v][i].to;         if (d[to] == inf) {           d[to] = d[v] + 1;           q.push(to);         }       }     }   }   void getAns() {     queue<int> q;     q.push(n - 1);     dp[n - 1] = 0;     while (!q.empty()) {       int v = q.front();       q.pop();       for (int i = 0; i < (int)g[v].size(); ++i) {         int to = g[v][i].to;         int z = 1 - g[v][i].z;         if (d[to] + 1 == d[v]) {           if (dp[to] > dp[v] + z) {             dp[to] = dp[v] + z;             pr[to] = v;           }           q.push(to);         }       }     }   }   int main() {     cin >> n >> m;     vert p;     int kol = 0;     for (int i = 0; i < m; ++i) {       int x, y, z;       scanf( %d %d %d , &x, &y, &z);       --x;       --y;       p.z = z;       p.num = i;       if (z == 0) {         ++kol;       }       p.to = y;       g[x].push_back(p);       p.to = x;       g[y].push_back(p);     }     go();     getAns();     vector<ans> out;     ans a;     int v = 0;     for (int to = pr[0]; to != -1; to = pr[to]) {       vert now;       for (int k = 0; k < g[v].size(); ++k) {         if (g[v][k].to == to) {           now = g[v][k];           break;         }       }       road[now.num] = true;       if (now.z == 0) {         a.x = v + 1;         a.y = to + 1;         a.z = 1;         out.push_back(a);       }       v = to;     }     for (int i = 0; i < n; ++i) {       for (int j = 0; j < (int)g[i].size(); ++j) {         if (road[g[i][j].num]) {           continue;         }         if (g[i][j].z == 1) {           a.x = i + 1;           a.y = g[i][j].to + 1;           a.z = 0;           road[g[i][j].num] = true;           out.push_back(a);         }       }     }     cout << out.size() <<   n ;     for (int i = 0; i < out.size(); ++i) {       cout << out[i].x <<     << out[i].y <<     << out[i].z <<   n ;     }     return 0;   }   