Find almost-shortest path more efficiently
Here's a partial/basic structured implementation of the problem. It works for the first two cases, but the last case comes back twice as large. I saw this question on SO and thought your version was highly over complicated and probably inefficient due to data structure choices. There isn't any reason to provide and pass around multi-dimensional vectors and such, and there's no doubt you could drop that priority_queue. 

Take a look at mine and see if you could simplify yours. Since your logic, I'm assuming, works you should be able to catch the last case without too much effort. I wasn't intending to finish it I just wanted to see if it could easily be done without such complexity. It isn't meant to replace yours, it's just to provide a second opinion on it. 

Take a look:

Note: Some of the variable are there because of the problem distription.
      Some validations are missing because the test data didn't require them.

#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;algorithm&gt;

using std::cin;
using std::cout;
using std::vector;
using std::sort;

const int START = 0;
const int END   = 1;
const int DIST  = 2;

vector&lt;int&gt; getPaths(int **, int, int, int);
int getDistance(int **, int , int , int , int , int&amp;);

int main (void)
{

    int input = 0;
    int n = 0, m = 0, s = 0, d = 0, u = 0, v = 0, p = 0; 
    int shortestPath = 0;
    int nextShortestPath = 0;
    int **pathPtr;
    vector&lt;int&gt; allDistances;

    cin &gt;&gt; n;
    if (n &gt;= 2 &amp;&amp; n &lt;= 500) {
        cin &gt;&gt; m;
        if (m &gt;= 1 &amp;&amp; m &lt;= 100000) {
            cin &gt;&gt; s;
            cin &gt;&gt; d;
            pathPtr = new int*[m];
            for (int i = 0; i &lt; m; ++i) {
                pathPtr[i] = new int[3];
            }
            for (int i = 0; i &lt; m; ++i) {
                for (int j = 0; j &lt; 3; ++j) {
                    cin &gt;&gt; input;
                    pathPtr[i][j] = input;
                }
            }
            allDistances = getPaths(pathPtr, m, s, d);
            sort(allDistances.begin(), allDistances.end());
            for (unsigned int i = 0; i &lt; allDistances.size(); ++i) {
                if (allDistances[i] != 0) {
                    shortestPath = allDistances[i];
                    if (i + 1 &lt; allDistances.size()) {
                        nextShortestPath = allDistances[i + 1];
                        break;
                    } else {
                        nextShortestPath = -1;
                        break;
                    }
                }
            }
            cout &lt;&lt; nextShortestPath;
        }
    }
    cin.get();
    return 0;
}

vector&lt;int&gt; getPaths(int **paths, const int m, const int s, const int d) {
    vector&lt;int&gt; distances;
    int distance = 0;
    int shortest = 0;
    int tempShort = 0;
    for (int i = 0; i &lt; m; ++i) {
        if (paths[i][START] == s) {
            distance = 0;
            if (paths[i][END] == d) {
                distances.push_back(paths[i][DIST]);
            } else {
                distances.push_back(getDistance(paths, i, i + 1, m, d, distance));
            }
        }
    }
    return distances;
}

int getDistance(int **paths, int i, int j, int m, int d, int &amp;distance) {
    if (paths[j][START] == paths[i][END]) {
        distance += paths[i][DIST];
        if (paths[j][END] != d) {
            if (j &lt; m) {
                distance += getDistance(paths, j, j + 1, m, d, distance);
            } else { 
                distance = 0;
            }
        } else {
            distance += paths[j][DIST];
        }
    } else {
        getDistance(paths, i, j + 1, m, d, distance);
    }
    return distance;
}


Let me know if it improved your running time any. Good Luck!