Bellman Ford

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main()
{
    int N = 0, M = 0;
    cin >> N >> M;
    vector <vector <pair <int, int> > > G(N);
    for (int i = 0; i < M; i++)
    {
        int from = 0, to = 0, w = 0;
        cin >> from >> to >> w;
        G[from].push_back(make_pair(to, w));
    }
    vector <int> R(N, (1 << 31 - 1));
    vector <int> P(N, -1);
    R[0] = 0;// 0 - starting peak
    queue <int> q;
    q.push(0);
    while (!q.empty())
    {
        int curent = q.front();
        q.pop();
        for (int i = 0; i < G[curent].size(); i++)
        {
            int to = G[curent][i].first;
            int w = G[curent][i].second;
            if (R[curent] + w < R[to])
            {
                R[to] = R[curent] + w;
                q.push(to);
                P[to] = curent;
            }
        }
    }

    for (int i = 0; i < P.size(); i++)
        cout << P[i] << " ";
    return 0;
}