用的 dijkstra，再加一个 road 数组

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, u, v, w, vis[N];
long long dis[N];
vector <int> road[N];
struct edge{
	int v, w;
};
struct node{
	int point, dist;
	bool operator > (const node& a) const{return dist > a.dist;}
};
vector <edge> vt[N];
priority_queue <node, vector <node>, greater <node> > q;
int main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	memset(dis, 0x3f, sizeof(dis));
	cin >> n >> m;
	while (m--){
		cin >> u >> v >> w;
		vt[u].push_back({v, w});
		vt[v].push_back({u, w});
	}
	dis[1] = 0;
	road[1].push_back(1);
	q.push({1, 0});
	while (!q.empty()){
		u = q.top().point;q.pop();
		if(vis[u]){
			continue;
		}
		vis[u] = 1;
		int len = vt[u].size();
		for (int i = 0; i < len; i++){
			v = vt[u][i].v, w = vt[u][i].w;
			if (dis[v] > dis[u] + w){
				road[v].resize(0);
				dis[v] = dis[u] + w;
				int len1 = road[u].size();
				for (int k = 0; k < len1; k++){
					road[v].push_back(road[u][k]);
				}
				road[v].push_back(v);
				q.push({v, dis[v]});
			}
		}
	}
	if (dis[n] == 0x3f3f3f3f3f3f3f3f){
		cout << "-1";
		return 0;
	}
	int len = road[n].size();
	for (int i = 0; i < len; i++){
		cout << road[n][i] << " ";
	}
	return 0;
}