Language: C++

#include "bits/stdc++.h"
using namespace std;

//#define int long long
#define DBG 1
#define dump(o) if(DBG){cerr<<#o<<" "<<(o)<<" ";}
#define dumpl(o) if(DBG){cerr<<#o<<" "<<(o)<<endl;}
#define dumpc(o) if(DBG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9 + 7);
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }

using Weight = int;
class Edge {
public:
	int s; //source
	int d; //destination
	Weight w; //weight
	Edge(int s = 0, int d = 0, Weight w = INF) : s(s), d(d), w(w) {};
	bool operator<(const Edge &e)const { return w < e.w; }
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;
using Array = vector<Weight>;
using Matrix = vector<Array>;
//辺の挿入
//G[s].emplace_back(s, d, w);
//G[d].emplace_back(d, s, w); 無向木は更に


enum { WHITE, GRAY, BLACK };
//未探索, 探索中, 探索済
//単一始点最短路(負閉路なし) Single Source Shortest Path
//Dijkstra O((E+V)logV)
//dist: 始点から各頂点までの最短距離 distance
//戻り値: 最短路木の親頂点(根は-1)
vector<int> dijkstra(const Graph &g, int s, vector<Weight> &dist) {
	using State = tuple<Weight, int, int>; //始点からの最小コスト 子 親
	priority_queue<State, vector<State>, greater<State>> PQ;
	int n = g.size();
	vector<int> color(n, WHITE);
	vector<int> prev(n, -1);
	dist.assign(n, INF);
	dist[s] = 0; PQ.emplace(0, s, -1); color[s] = GRAY; //始点
	while (PQ.size()) {
		Weight d; int v, u;
		tie(d, v, u) = PQ.top(); PQ.pop(); //distが最小となるStateを取り出し
		if (dist[v] < d)continue; //すでに最短でなければ無視
		color[v] = BLACK;
		prev[v] = u;
		for (auto &e : g[v]) { //隣接する頂点が存在する限り		
			if (color[e.d] == BLACK)continue; //探索済は無視
			if (dist[e.d] > dist[v] + e.w) {
				dist[e.d] = dist[v] + e.w;
				PQ.emplace(dist[e.d], e.d, v);
				color[e.d] = GRAY;
			}
		}
	}
	return prev;
}

//単一始点最短路(負閉路あり) Single Source Shortest Path
//Bellman Ford O(VE)
//dist: 始点から各頂点までの最短距離
//戻り値: 最短路木の親頂点, 負閉路なし:true あり:false
pair<vector<Weight>, bool> bellman_ford(const Graph &g, int s, vector<Weight> &dist) {
	int n = g.size();
	vector<int> prev(n, -1);
	Edges es; for (int i = 0; i < n; i++) for (auto &e : g[i]) es.emplace_back(e);
	dist.assign(n, INF); dist[s] = 0;
	bool negative_cycle = false;
	for (int i = 0;; i++) {
		bool update = false;
		for (auto &e : es) {
			if (dist[e.s] != INF && dist[e.d] > dist[e.s] + e.w) {
				dist[e.d] = dist[e.s] + e.w;
				prev[e.d] = e.s;
				update = true;
			}
		}
		if (!update) break;
		if (i > n) { negative_cycle = true; break; }
	}
	return make_pair(prev, !negative_cycle);
}

//始点から終点までの経路を取得
//終点から親を再帰的に辿り始点に着くまでの経路を反転している
//存在しない場合の戻り値: vector<int>()
vector<int> get_path(int s, int d, vector<int> prev) {
	vector<int> path;
	path.emplace_back(d);
	for (int i = d; i != s; ) {
		if (i == -1)return vector<int>();
		path.emplace_back(i = prev[i]);
	}
	reverse(path.begin(), path.end());
	return path;
}

vector<vector<vector<int>>> warshall_floyd(const Graph &g, Matrix &dist) {
	int n = g.size();
	dist.assign(n, Array(n, INF));
	vector<vector<vector<int>>> prev(n, vector<vector<int>>(n, vector<int>()));
	for (int i = 0; i < n; i++) dist[i][i] = 0;
	for (int i = 0; i < n; i++)
		for (auto e : g[i]) {
			if (chmin(dist[e.s][e.d], e.w)) {
				prev[e.s][e.d] = vector<int>{ e.d };
			}
		}
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			for (int k = 0; k < n; k++)
				if (dist[j][i] != INF&&dist[i][k] != INF) {
					if (chmin(dist[j][k], dist[j][i] + dist[i][k])) {
						prev[j][k] = prev[j][i];
						prev[j][k].insert(prev[j][k].begin(), all(prev[i][k]));
					}
				}
	return prev;
}

//トポロジカルソート O(E+V)
//入次数が0の点と辺を取り除きながらretに突っ込む
vector<int> topological_sort(const Graph &g) {
	int n = g.size(), k = 0;
	vector<int> ord(n), indeg(n); //入次数
	for (auto &es : g) for (auto &e : es) indeg[e.d]++;
	queue<int> Q;
	for (int i = 0; i < n; i++) if (indeg[i] == 0) Q.push(i);
	while (!Q.empty()) {
		int v = Q.front(); Q.pop(); ord[k++] = v;
		for (auto &e : g[v]) if (--indeg[e.d] == 0) Q.push(e.d);
	}
	return *max_element(indeg.begin(), indeg.end()) == 0 ? ord : vector<int>();
}

//木の直径
Edge diameter(const Graph &g, int s = 0) {
	vector<Weight> dist;
	dijkstra(g, s, dist);
	int n = g.size(), u = -1, v = -1;
	for (int i = 0; i < n; i++) if (dist[i] != INF && (u == -1 || dist[i] > dist[u])) u = i;
	dijkstra(g, u, dist);
	for (int i = 0; i < n; i++) if (dist[i] != INF && (v == -1 || dist[i] > dist[v])) v = i;
	Weight d = dist[v];
	if (u > v) swap(u, v);
	return Edge(u, v, d);
}

//#include "UnionFind.cpp"
////最小全域木
////Kruskal O(|E|log|E|)
//pair<Weight, Edges> kruskal(const Graph &g) {
//	UnionFind UF(g.size());
//	Edges es;
//	for (int i = 0; i < g.size(); i++) for (auto &e : g[i]) es.emplace_back(e);
//	sort(es.begin(), es.end());
//	Weight total = 0;
//	Edges T;
//	for (auto &e : es) if (!UF.same(e.s, e.d)) {
//		T.push_back(e); total += e.w; UF.unite(e.s, e.d);
//	}
//	return make_pair(total, T);
//}
//
////最小全域木
////Prim O(ElogV)
////rから到達可能な頂点が対象
////Edgeを bool operator<(const Edge &e)const { return w > e.w; } にする必要がある
//pair<Weight, Edges> prim(const Graph &g, int r = 0) {
//	Edges T; Weight total = 0; vector<int> v(g.size());
//	priority_queue <Edge> q;
//	q.emplace(-1, r, 0);
//	while (q.size()) {
//		Edge e = q.top(); q.pop();
//		if (v[e.d]) continue;
//		v[e.d] = true;
//		total += e.w; if (e.s != -1) T.emplace_back(e);
//		for (auto &f : g[e.d]) if (!v[f.d]) q.emplace(f);
//	}
//	return make_pair(total, T);
//}

signed main() {
	int N, M; cin >> N >> M;
	Graph G(N);
	rep(i, 0, M) {
		int a, b, c; cin >> a >> b >> c; a--, b--;
		G[a].emplace_back(a, b, c);
		G[b].emplace_back(b, a, c);
	}
	Matrix dist;
	auto prev = warshall_floyd(G, dist);
	unordered_set<pair<int, int>> st;
	rep(i, 0, N)rep(j, i + 1, N) {
		prev[i][j].emplace_back(i);
		rep(k, 1, prev[i][j].size()) {
			int s = prev[i][j][k - 1], d = prev[i][j][k];
			if (s > d)swap(s, d);
			st.insert(make_pair(s, d));
		}
	}
	cout << M - st.size() << endl;
	return 0;
}

Compiler output:
a.cc: In function 'int main()':
a.cc:201:39: error: use of deleted function 'std::unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set() [with _Value = std::pair<int, int>; _Hash = std::hash<std::pair<int, int> >; _Pred = std::equal_to<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >]'
  201 |         unordered_set<pair<int, int>> st;
      |                                       ^~
In file included from /usr/include/c++/14/unordered_set:41,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:189,
                 from a.cc:1:
/usr/include/c++/14/bits/unordered_set.h:142:7: note: 'std::unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set() [with _Value = std::pair<int, int>; _Hash = std::hash<std::pair<int, int> >; _Pred = std::equal_to<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >]' is implicitly deleted because the default definition would be ill-formed:
  142 |       unordered_set() = default;
      |       ^~~~~~~~~~~~~
/usr/include/c++/14/bits/unordered_set.h: At global scope:
/usr/include/c++/14/bits/unordered_set.h:142:7: error: use of deleted function 'std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::_Hashtable() [with _Key = std::pair<int, int>; _Value = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; _ExtractKey = std::__detail::_Identity; _Equal = std::equal_to<std::pair<int, int> >; _Hash = std::hash<std::pair<int, int> >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, true, true>]'
In file included from /usr/include/c++/14/bits/unordered_map.h:33,
                 from /usr/include/c++/14/unordered_map:41,
                 from /usr/include/c++/14/functional:63,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:53:
/usr/include/c++/14/bits/hashtable.h:539:7: note: 'std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::_Hashtable() [with _Key = std::pair<int, int>; _Value = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; _ExtractKey = std::__detail::_Identity; _Equal = std::equal_to<std::pair<int, int> >; _Hash = std::hash<std::pair<int, int> >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, true, true>]' is implicitly deleted because the default definition would be ill-formed:
  539 |       _Hashtable() = default;
      |       ^~~~~~~~~~
/usr/include/c++/14/bits/hashtable.h:539:7: error: use of deleted function 'std::__detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _Traits>::_Hashtable_base() [with _Key = std::pair<int, int>; _Value = std::pair<int, int>; _ExtractKey = std::__detail::_Identity; _Equal = std::equal_to<std::pair<int, int> >; _Hash = std::hash<std::pair<int, int> >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _Traits = std::__detail::_Hashtable_traits<true, true, true>]'
In file included from /usr/include/c++/14/bits/hashtable.h:35:
/usr/include/c++/14/bits/hashtable_policy.h:1731:7: note: 'std::__detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _Traits>::_Hashtable_base() [with _Key = std::pair<int, int>; _Value = std::pair<int, int>; _ExtractKey = std::__detail::_Identity; _Equal = std::equal_to<std::pair<int, int> >; _Hash = std::hash<std::pair<int, int> >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _Traits = std::__detail::_Hashtable_traits<true, true, true>]' is implicitly deleted because the default definition would be ill-formed:
 1731 |       _Hashtable_base() = default;
      |       ^~~~~~~~~~~~~~~
/usr/include/c++/14/bits/hashtable_policy.h:1731:7: error: use of deleted function 'std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, _Unused, __cache_hash_code>::_Hash_code_base() [with _Key = std::pair<int, int>; _Value = std::pair<int, int>; _ExtractKey = std::__detail::_Identity; _Hash = std::hash<std::pair<int, int> >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; bool __cache_hash_code = true]'
/usr/include/c++/14/bits/hashtable_policy.h: In instantiation of 'std::__detail::_Hashtable_ebo_helper<_Nm, _Tp, true>::_Hashtable_ebo_helper() [with int _Nm = 1; _Tp = std::hash<std::pair<int, int> >]':
/usr/include/c++/14/bits/hashtable_policy.h:1328:7:   required from here
 1328 |       _Hash_code_base() = default;
      |       ^~~~~~~~~~~~~~~
/usr/include/c++/14/bits/hashtable_policy.h:1245:49: error: use of deleted function 'std::hash<std::pair<int, int> >::hash()'
 1245 |       _Hashtable_ebo_helper() noexcept(noexcept(_Tp())) : _Tp() { }
      |                                                 ^~~~~
In file included from /usr/include/c++/14/string_view:50,
                 from /usr/include/c++/14/bits/basic_string.h:47,
                 from /usr/include/c++/14/string:54,
                 from /usr/include/c++/14/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:52:
/usr/include/c++/14/bits/functional_hash.h:102:12: note: 'std::hash<std::pair<int, int> >::hash()' is implicitly deleted because the default definition would be ill-formed:
  102 |     struct hash : __hash_enum<_Tp>
      |            ^~~~
/usr/include/c++/14/bits/functional_hash.h:102:12: error: no matching function for call to 'std::__hash_enum<std::pair<int, int>, false>::__hash_enum()'
/usr/include/c++/14/bits/functional_hash.h:83:7: note: candidate: 'std::__hash_enum<_Tp, <anonymous> >::__hash_enum(std::__hash_enum<_Tp, <anonymous> >&&) [with _Tp = std::pair<int, int>; bool <anonymous> = false]'
   83 |       __hash_enum(__hash_enum&&);
      |       ^~~~~~~~~~~
/usr/include/c++/14/bits/functional_hash.h:83:7: note:   candidate expects 1 argument, 0 provided
/usr/include/c++/14/bits/functional_hash.h:102:12: error: 'std::__hash_enum<_Tp, <anonymous> >::~__hash_enum() [with _Tp = std::pair<int, int>; bool <anonymous> = false]' is private within this context
  102 |     struct hash : __hash_enum<_Tp>
      |            ^~~~
/usr/include/c++/14/bits/functional_hash.h:84:7: note: declared private here
   84 |       ~__hash_enum();
      |       ^
/usr/include/c++/14/bits/hashtable_policy.h:1245:49: note: use '-fdiagnostics-all-candidates' to display considered candidates
 1245 |       _Hashtable_ebo_helper() noexcept(noexcept(_Tp())) : _Tp() { }
      |                                                 ^~~~~
/usr/include/c++/14/bits/hashtable_policy.h:1328:7: note: 'std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, _Unused, __cache_hash_code>::_Hash_code_base() [with _Key = std::pair<int, int>; _Value = std::pair<int, int>; _ExtractKey = std::__detail::_Identity; _Hash = std::hash<std::pair<int, int> >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; bool __cache_hash_code = true]' is implicitly deleted because the default definition would be ill-formed:
 1328 |       _Hash_code_base() = default;
      |       ^~~~~~~~~~~~~~~
/usr/include/c++/14/bits/hashtable_policy.h:1328:7: error: use of deleted function 'std::__detail::_Hashtable_ebo_helper<1, std::hash<std::pair<int, int> >, true>::~_Hashtable_ebo_helper()'
/usr/include/c++/14/bits/hashtable_policy.h:1242:12: note: 'std::__detail::_Hashtable_ebo_helper<1, std::hash<std::pair<int, int> >, true>::~_Hashtable_ebo_helper()' is implicitly deleted because the default definition would be ill-formed:
 1242 |     struct _Hashtable_ebo_helper<_Nm, _Tp, true>
      |            ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/hashtable_policy.h:1242:12: error: use of deleted function 'std::hash<std::pair<int, int> >::~hash()'
/usr/include/c++/14/bits/functional_hash.h:102:12: note: 'std::hash<std::pair<int, int> >::~hash()' is implicitly deleted because the default definition would be ill-formed:
  102 |     struct hash : __hash_enum<_Tp>
      |            ^~~~
/usr/include/c++/14/bits/functional_hash.h:102:12: error: 'std::__hash_enum<_Tp, <anonymous> >::~__hash_enum() [with _Tp = std::pair<int, int>; bool <anonymous> = false]' is private within this context
/usr/include/c++/14/bits/functional_hash.h:84:7: note: declared private here
   84 |       ~__hash_enum();
      |       ^
/usr/include/c++/14/bits/hashtable_policy.h:1731:7: note: use '-fdiagnostics-all-candidates' to display considered candidates
 1731 |       _Hashtable_base() = default;
      |       ^~~~~~~~~~~~~~~
/usr/include/c++/14/bits/hashtable_policy.h:1731:7: error: use of deleted function 'std::__detail::_Hash_code_base<std::pair<int, int>, std::pair<int, int>, std::__detail::_Identity, std::hash<std::pair<int, int> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, true>::~_Hash_code_base()'
/usr/include/c++/14/bits/hashtable_policy.h:1306:12: note: 'std::__detail::_Hash_code_base<std::pair<int, int>, std::pair<int, int>, std::__detail::_Identity, std::hash<std::pair<int, int> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, true>::~_Hash_code_base()' is implicitly deleted because the default definition would be ill-formed:
 1306 |     struct _Hash_code_base
      |            ^~~~~~~~~~~~~~~
/usr/include/c++/14/bits/hashtable_policy.h:1306:12: error: use of deleted function 'std::__detail::_Hashtable_ebo_helper<1, std::hash<std::pair<int, int> >, true>::~_Hashtable_ebo_helper()'
/usr/include/c++/14/bits/hashtable.h:539:7: note: use '-fdiagnostics-all-candidates' to display considered candidates
  539 |       _Hashtable() = default;
      |       ^~~~~~~~~~
/usr/include/c++/14/bits/hashtable.h:539:7: error: use of deleted function 'std::__detail::_Hashtable_base<std::pair<int, int>, std::pair<int, int>, std::__detail::_Identity, std::equal_to<std::pair<int, int> >,