func_code_string: #include <bits/stdc++.h>   using namespace std;   const int MAXN = 100010;   const int MAXM = 100010;   const int INF = 1000000000;   int dist[MAXN], dp[MAXN];   pair<int, int> par[MAXN];   bool marked[MAXM];   vector<pair<int, int> > edges[MAXN];   queue<int> q;   vector<pair<int, int> > v;   int x[MAXM], y[MAXM], z[MAXM];   int n, m;   void bfs(int s) {     for (int i = 0; i < n; i++) dist[i] = INF;     dist[s] = 0;     q.push(s);     while (!q.empty()) {       int v = q.front();       q.pop();       for (int i = 0; i < edges[v].size(); i++) {         int u = edges[v][i].first;         if (dist[u] > dist[v] + 1) {           dist[u] = dist[v] + 1;           q.push(u);         }       }     }   }   int main() {     cin >> n >> m;     int working = 0;     for (int i = 0; i < m; i++) {       cin >> x[i] >> y[i] >> z[i];       x[i]--, y[i]--;       working += z[i];       edges[x[i]].push_back(pair<int, int>(y[i], i));       edges[y[i]].push_back(pair<int, int>(x[i], i));     }     bfs(0);     for (int i = 0; i < n; i++) {       v.push_back(pair<int, int>(dist[i], i));       dp[i] = INF;     }     sort(v.begin(), v.end());     dp[0] = 0;     for (int i = 0; i < n; i++) {       int u = v[i].second;       for (int j = 0; j < edges[u].size(); j++) {         int q = edges[u][j].first;         int w = 1 - z[edges[u][j].second];         if (dist[q] == dist[u] + 1 && dp[q] > dp[u] + w) {           par[q] = pair<int, int>(u, edges[u][j].second);           dp[q] = dp[u] + w;         }       }     }     int now = n - 1;     while (now != 0) {       marked[par[now].second] = true;       now = par[now].first;     }     cout << working - dist[n - 1] + dp[n - 1] * 2 << endl;     for (int i = 0; i < m; i++)       if (marked[i] ^ z[i])         cout << x[i] + 1 <<     << y[i] + 1 <<     << 1 - z[i] << endl;   }   