Алгоритм Дейкстры

Мне нужно восстановить минимальный путь в графе, от вершины s до f, используя алгоритм Дейкстры. Моя идея - запоминать вершину-родителя для каждой вершины, относительно минимального расстояния для которой мы уверены. Решение не проходит половину тестов, не могли вы помочь мне, указав на ошибку?

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <iterator>
using namespace std;
vector<vector<long long> > graph;
vector<long long> dist;
vector<long long> used;
vector<long long> parrent;
void djkstera(long long u, long long &n, long long &v){
    set<pair<long long, long long> > que;
    que.insert({0, u});
    dist[u] = 0;
    long long parr = u;
    while(!que.empty()){
        while(!que.empty() && used[(*que.begin()).second]){
            que.erase(que.begin());
        }
        if(que.empty())
            break;
        u = (*que.begin()).second;
        used[u] = true;
        parrent[u] = parr;
        parr = u;
        que.erase(que.begin());
        for(long long i = 0; i < n; ++i){
            if(graph[u][i] != -1 and u!=i){
                dist[i] = min(dist[i], dist[u] + graph[u][i]);
                que.insert({dist[i], i});
            }
        }
    }
}
int main() {
    long long n,s,f;
    cin >> n >> s >> f; // s - start, f - finish
    s--; f--;
    graph.assign(n, vector<long long>(n));
    used.assign(n, false);
    dist.assign(n, INT64_MAX);
    parrent.resize(n);
    //Граф задаётся матрицой смежности
    for(long long i = 0; i < n; ++i){
        for(long long j = 0; j < n; ++j){
            cin >> graph[i][j];
        }
    }
    djkstera(s, n, f);
    //Пути не существует
    if(dist[f] == INT64_MAX){
        cout << "No solution";
        return 0;
    }
    vector<long long> res;
    for(long long i = f; i != s; i = parrent[i]){
         res.push_back(i + 1);
    }
    res.push_back(s + 1);
    reverse(res.begin(), res.end());
    copy(res.begin(), res.end(), ostream_iterator<long long>(cout, " "));
    return 0;
}