I have a directed graph which has cycles. All edges are weighted, and the weights can be negative. There can be negative cycles.

I want to find a path from s to t, which minimizes the total weight on the path. Sure, it can go to negative infinity when negative cycles exist. But what if I disallow cycles in the path (not in the original graph)? That is, once the path leaves a node, it can not enter the node again.

This surely avoids the negative infinity problem, but surprisingly no known algorithm is found by a search on Google. The closest is Floyd–Warshall algorithm, but it does not allow negative cycles.

Thanks a lot in advance.

Edit: I may have generalized my original problem too much. Indeed, I am given a cyclic directed graph with nonnegative edge weights. But in addition, each node has a positive reward too. I want to find a simple path which minimizes (sum of edge weights on the path) - (sum of node rewards covered by the path). This can be surely converted to the question that I posted, but some structure is lost. And some hint from submodular analysis suggests this motivating problem is not NP-hard. Thanks a lot