#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
const int mxa = 1e5 + 1;
ll a, b, c, n, m;
vector <ar<ll, 2>> adj[mxa];
ll dist[mxa];
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> a >> b >> c; --a, --b;
adj[a].push_back({c, b});
}
memset(dist, 0x3f, sizeof(dist));
priority_queue< ar<ll, 2> , vector<ar<ll, 2>>, greater<ar<ll, 2>> > pq;
dist[0] = 0;
pq.push({0, 0});
while (pq.size()) {
ar<ll, 2> node = pq.top();
pq.pop();
if (node[0] > dist[node[1]])continue;
for ( ar<ll, 2> child : adj[node[1]]) {
if (dist[child[1]] > node[0] + child[0]) {
dist[child[1]] = node[0] + child[0];
pq.push({dist[child[1]], child[1]});
}
}
}
for (int i = 0; i < n; i++) cout << dist[i] << " ";
}
I have implemented code for Dijstra ,but it finds only min distance of each node from source node. could anyone please help how to retace the shortest path in this approach .Thank you