We assume that edge weights are positive integers. Given a directed graph G with edge weights, call an edge e redundant if e does not belong to any minimum-weight strongly-connected spanning subgraphs of G.
We claim that unless P=NP, there is no polynomial-time algorithm that always finds a redundant edge in a given directed graph with edge weights as long as there is one. More precisely:
Theorem. Given a directed graph G with edge weights, it is NP-hard to find a redundant edge in G or declare that G does not have a redundant edge.
Proof. The key observation is that if G has a unique minimum-weight strongly-connected spanning subgraph, then you can compute that subgraph by removing the redundant edges one by one. Therefore, it remains to show that the uniqueness does not make the minimum-weight strongly-connected spanning subgraph problem any easier, but this is proved by the next Lemma. QED.
Lemma. Given a directed graph G with edge weights, it is NP-hard to compute the weight of the minimum-weight strongly-connected spanning subgraph of G even under the promise that G has a unique minimum-weight strongly-connected spanning subgraph.
Proof. As you know, the problem without the promise is NP-hard (even for the unit-weight case) by a reduction from the Hamiltonian circuit problem. We reduce the problem without the promise to the problem with the promise.
Let G be a directed graph with edge weights. Label the edges of G by e0, e1, …, em−1, where m is the number of edges in G. Let wi be the given weight of the edge ei. Let the new weight w′i=2mwi+2i. Then it is easy to verify that G with the new weights has a unique minimum-weight strongly-connected spanning subgraph. It is also easy to verify that the minimum weight W of a strongly-connected spanning subgraph in G with the original weights can be computed from the minimum weight W′ in G with the new weights as W=⌊W′/2m⌋. QED.