Hint
Dijkstra from vertex 1 with an array prev. At the relaxation dist[u] = dist[v] + w also write prev[u] = v. At the end go from n through prev to 1 and reverse the array. (The path 1–2–4–5 has the same length 9; this program prints the one that was found first.)
Solution (C++)
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const long long INF = 1e18;
int main() {
int n, m;
cin >> n >> m;
vector<vector<pair<int, int>>> graph(n + 1);
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
graph[u].push_back({v, w});
graph[v].push_back({u, w});
}
vector<long long> dist(n + 1, INF);
vector<int> prev(n + 1, 0);
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
dist[1] = 0;
pq.push({0, 1});
while (!pq.empty()) {
auto [d, v] = pq.top();
pq.pop();
if (d > dist[v]) continue;
for (auto [u, w] : graph[v])
if (dist[v] + w < dist[u]) {
dist[u] = dist[v] + w;
prev[u] = v; // we reached u by the shortest way from v
pq.push({dist[u], u});
}
}
if (dist[n] == INF) {
cout << -1 << endl;
return 0;
}
vector<int> path;
for (int v = n; v != 0; v = prev[v]) path.push_back(v);
reverse(path.begin(), path.end());
cout << dist[n] << endl;
for (size_t i = 0; i < path.size(); i++) cout << path[i] << (i + 1 < path.size() ? " " : "\n");
return 0;
}