RT，这份代码在极端数据（一条链，$n=10^5,m=n-1$，test 37、38）会 MLE。

虽然已经特判过了，但是还是求问 MLE 原因。

// LUOGU_RID: 125399880
#include<bits/stdc++.h>

using namespace std;
const int MAXN = 1e5 + 5;
int n, m, ans = 2e9, pp = 2e9;
int dis[MAXN], _dis[MAXN];
bool vis[MAXN];
struct Node{
  int x, y, p;
} b[MAXN];
vector<Node> a[MAXN];
vector<int> qout[MAXN];
/*
void dfs(int x, int cnt, vector<int> p){
  if (vis[x]){
    return ;
  }
  if (x == 1){
    int op = check(p);
    //cerr << op << ' ' << cnt << '\n' << '\n';
    if (ans > cnt){
      ans = cnt, pp = op, out = p;
    }else if (ans == cnt && pp > op){
      pp = op, out = p;
    }
    return ;
  }
  vis[x] = 1;
  for (auto v : a[x]){
    p[v.p] = 1;
    dfs(v.x, cnt + 1, p);
    p[v.p] = 0;
  }
  vis[x] = 0;
}
*/

int jl(int x, int l, int id, int _l, int from){
  int op = b[id].p ? _l - 1 : _l + 1;
  if (l > dis[x] || (op >= _dis[x] && l == dis[x])){
    return 0;
  }
  qout[x] = qout[from];
  qout[x].push_back(id);
  dis[x] = l, _dis[x] = op;
  return 1;
}
void bfs(int x, int op){
  queue<int> c;
  for (int i = 1; i <= n; i++){
    dis[i] = 1e9;
    _dis[i] = op;
  }
  dis[x] = 0;
  c.push(x);
  while (c.size()){
    auto p = c.front();
    c.pop();
    for (auto v : a[p]){
      if (jl(v.x, dis[p] + 1, v.p, _dis[p], p)){
        c.push(v.x); 
      }
    }
    if (p != 1){
      qout[p].clear();
    }
    
  }
}
int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  int _op = 0;
  for (int i = 1, u, v, w; i <= m; i++){
    cin >> u >> v >> w;
    _op += w;
    b[i] = {u, v, w};
    a[u].push_back({v, w, i});
    a[v].push_back({u, w, i});
  }
  bfs(n, _op);
  cout << _dis[1] << '\n';
  for (auto v : qout[1]){
    vis[v] = 1;
  }
  for (int i = 1; i <= m; i++){
    if (b[i].p ^ vis[i]){
      cout << b[i].x << ' ' << b[i].y << ' ' << !b[i].p << '\n';
    }
  }
  return 0;
}

（放的是 MLE on test 37 的代码）