dijkstra.cpp

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
const ll INF = LLONG_MAX;

vector<pll> graph[100001];     // Adjacency list (node, cost)
vector<ll> dist(100001, INF);  // Distance array initialized to INF
vector<ll> sum(100001, 0);     // To track number of shortest paths to each node
vector<int> par(100001, -1);   // To track the parent of each node for path reconstruction
vector<bool> vis(100001, false); // To check if node is visited

// Dijkstra's Algorithm
void bfs_dijkstra(int src) {
    priority_queue<pll, vector<pll>, greater<pll>> pq;  // Min-heap priority queue
    dist[src] = 0;
    pq.push({0, src});  // Push the source with distance 0

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        if (vis[u]) continue; 
        vis[u] = true;

        // Explore neighbors
        for (auto i : graph[u]) {
            int v = i.first;    // Neighbor node
            ll cost = i.second; // Edge weight between u and v

            // If we find a shorter path to v via u
            if (dist[u] + cost < dist[v]) {
                dist[v] = dist[u] + cost;
                pq.push({dist[v], v});
                par[v] = u;      // Update parent for path reconstruction
                sum[v] = 1;      // First shortest path to v
            } 
            // If there's another shortest path of the same length
            else if (dist[u] + cost == dist[v]) {
                sum[v]++;  // Increment count of shortest paths to v
            }
        }
    }
}

// Function to print the path from source to destination
void print_path(int src, int dest) {
    vector<int> path;
    for (int v = dest; v != -1; v = par[v]) {
        path.push_back(v);
    }
    reverse(path.begin(), path.end());

    for (int node : path) {
        cout << node << " ";
    }
    cout << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, e;
    cin >> n >> e;  

    for (int i = 0; i < e; i++) {
        int u, v;
        ll cost;
        cin >> u >> v >> cost;
        graph[u].push_back({v, cost});
        graph[v].push_back({u, cost});  // Because it's an undirected graph
    }

    bfs_dijkstra(1);  // Find shortest paths starting from node 1

    if (dist[n] == INF) {
        cout << -1 << endl;  // If node n is unreachable, print -1
    } else {
        cout << dist[n] << endl;  // Print the shortest distance to node n
        print_path(1, n);         // Print the path from node 1 to node n
    }

    return 0;
}