Сначало нам нужно минимизировать количество пройденных "-1", а потом сумму остальных штрафов. Заменим все "-1" на число $10^{10}$ и найдем минимальный путь из левой верхней в правую нижнюю Дийкстрой с кучей(все штрафы у нас неотрицательны). На сколько Вы знаете, Дийкстра с кучей работает за $O(M log N)$, а так как количество ребер у нас пропорционально количеству вершин, то все получится. У меня почему-то не проходило решение с std::set на Си++, потом зашло на std::priority_queue. Также можно попасть на ML. У меня он был и мне пришлось работать с неявным графом, у других может проходило и тупо.