SPFA 做最短路计数是错的。具体可以见上一个讨论。

经过 UOJ 群的讨论，发现其中只有第三种解法是正确的，复杂度与普通 SPFA 相同，所以可以被卡到 $O(nm)$，在此题中不应该被放过。（不过个人认为这种做法仍有学习意义，可以保留一篇）所以请求撤下所有 SPFA 题解，并添加相应的 hack 数据：

Input:

4 4
1 3 2
1 2 1
2 3 1
3 4 3

Output:

5 2

Input:

4 4
1 2 1
2 3 1
1 3 2
3 4 3

Output：

5 2

(上面两个数据本质上是一样的，但由于存图顺序的问题，第一个点被用于卡链式前向星，第二个点被用于卡 vector。至于邻接举证两个都可以卡。)

以及用以下代码造的数据：

#include <bits/stdc++.h>
using namespace std;
struct edge {
  int u, v, w;
};
vector<edge> v;
int id[5000][5000], n = 50, tp, m = 2000 / n, a[1000000];
int r() {
  return rand();
  // return rand()<<13|rand();
}
int main() {
  freopen("spfa1.in", "w", stdout);
  srand(time(0));
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j) id[i][j] = ++tp, a[tp] = tp;
  //	random_shuffle(a+1,a+tp+1);
  int SIZE = 29989;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j) {
      if (i < n) {
        v.push_back(edge{id[i][j], id[i + 1][j], 1});
        v.push_back(edge{id[i + 1][j], id[i][j], 1});
        if (j < m) {
          if (1)
            v.push_back(edge{id[i][j], id[i + 1][j + 1], r() % SIZE + 10});
          else
            v.push_back(edge{id[i + 1][j + 1], id[i][j], r() % SIZE + 10});
        }
      }
      if (j < m) {
        v.push_back(edge{id[i][j], id[i][j + 1], r() % SIZE + 10});
        v.push_back(edge{id[i][j + 1], id[i][j], r() % SIZE + 10});
      }
    }
  fprintf(stderr, "[%d,%d,%d]", v.size(), n, m);
  random_shuffle(v.begin(), v.end());
  //	printf("%d %d %d\n",tp,v.size(),2);
  printf("%d %d\n", tp, v.size());
  for (int i = 0; i < v.size(); ++i)
    printf("%d %d %d\n", a[v[i].u], a[v[i].v], v[i].w);
  //	for(int i=1;i<=10;++i)printf("%d ",a[id[1][10*i]]);
  //	printf("%d %d",a[1],a[2]);
}

以上。

@StudyingFather