1) Don't forget, that you have a directed graph!
2) Also don't forget, that standard C++ streams(cin and cout) are very slow! Use scanf and printf.
3) And just use Bellman–Ford algorithm. It works by O(n*m) - in the worst case.

Edited by author 08.05.2012 13:16