Pruning a strongly connected digraph
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.