Вывод пути алгоритма Дейкстры

#include "stdafx.h"
#include <iostream>
#include <queue> 
#include <vector>
using namespace std;
int main()
{
    int a;
    cout << "Vvedite kol-vo vershin: ";
    cin >> a;
    int c;
    cout << "Vvedite kol-vo reber: ";
    cin >> c;
    vector<vector<int>>v(c + 1, vector<int>(c + 1, 0));
 
    cout << "Vershina| Vershina| Rasstoyanie" << endl;
 
    for (int i = 0; i < c; i++) {
        int z, x, r;
        cin >> z >> x >> r;
        v[z][x] = v[x][z] = r;
    }
 
    bool poseshenie[100]; // Для проверки посещена ли вершина
    int rasstoyanie[100];
 
    for (int i = 0; i < c; i++) { // Присваиваем каждой вершине бесконечность
        poseshenie[i] = false;
        rasstoyanie[i] = INT_MAX;
    }
 
    rasstoyanie[1] = 0; // Входим в первую вершину, ставим мин расстояние
    poseshenie[1] = true; // Помечаем как посещенную 
 
    queue<int>q; // Подключаем очередь
    q.push(1);
 
    while (!q.empty()) { // Цикл, заключающийся в обходе вершин
        int versh = q.front(); // Достаем первую из очереди
        q.pop(); // Удаляем ее из очереди
        for (int j = 1; j < v[versh].size(); j++) { // Цикл прохождения вершин, Size указывает на смежные вершины
            if (!poseshenie[j] && v[versh][j] && v[versh][j] + rasstoyanie[versh] < rasstoyanie[j]) { // Ставим условия заходим только если вершина не посещена, с этой вершиной есть ребро, расстояние между вершинами меньше чем уже существует
                rasstoyanie[j] = v[versh][j] + rasstoyanie[versh];
                q.push(j);
            }
        }
    }
    cout << "Vivod kratchaishego pyti: " << endl; // выводим расстояние от первой вершины до всех остальных 
    for (int j = 2; j < a + 1; j++) {
        cout << "Rasstoyanie do " << j<< " vershini ravno " << rasstoyanie[j] << endl;
    }
 
    system("pause");
    return 0;
}

#include "stdafx.h"
#include <iostream>
#include <queue> 
#include <vector>
#include <string>
using namespace std;
int main()
{
    int a;
    cout << "Vvedite kol-vo vershin: ";
    cin >> a;
    int c;
    cout << "Vvedite kol-vo reber: ";
    cin >> c;
    vector<vector<int>>v(c + 1, vector<int>(c + 1, 0));
 
    cout << "Vershina| Vershina| Rasstoyanie" << endl;
 
    for (int i = 0; i < c; i++) {
        int z, x, r;
        cin >> z >> x >> r;
        v[z][x] = v[x][z] = r;
    }
 
    bool poseshenie[100]; // Для проверки посещена ли вершина
    int rasstoyanie[100];
    string path[100];
    for (int i = 0; i < c; i++) { // Присваиваем каждой вершине бесконечность
        poseshenie[i] = false;
        rasstoyanie[i] = INT_MAX;
    }
 
    rasstoyanie[1] = 0; // Входим в первую вершину, ставим мин расстояние
    poseshenie[1] = true; // Помечаем как посещенную 
 
    queue<int>q; // Подключаем очередь
    q.push(1);
    path[1]=to_string(1);
    while (!q.empty()) { // Цикл, заключающийся в обходе вершин
        int versh = q.front(); // Достаем первую из очереди
        q.pop(); // Удаляем ее из очереди
        for (int j = 1; j < v[versh].size(); j++) { // Цикл прохождения вершин, Size указывает на смежные вершины
            if (!poseshenie[j] && v[versh][j] && v[versh][j] + rasstoyanie[versh] < rasstoyanie[j]) { // Ставим условия заходим только если вершина не посещена, с этой вершиной есть ребро, расстояние между вершинами меньше чем уже существует
                rasstoyanie[j] = v[versh][j] + rasstoyanie[versh];
                path[j]=path[versh]+"-"+to_string(j);
                q.push(j);
            }
        }
    }
    cout << "Vivod kratchaishego pyti: " << endl; // выводим расстояние от первой вершины до всех остальных 
    for (int j = 2; j < a + 1; j++) {
        cout << "Rasstoyanie do " << j<< " vershini ravno " << rasstoyanie[j] << endl;
        cout << "path do " << j<< " vershini ravno " << path[j] << endl;
    }
 
    system("pause");
    return 0;
}