只有 10 分，求调。

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node{
	int fi,se;
	bool operator<(const node &T)const{
		return fi>T.fi;
	}
};
int n,m,dis[105],fa[125];
bool vis[105];
vector<node>v[105];
vector<int>ans;
void Dijkstra(int Begin){
	fill(dis,dis+n+1,-1e18);
	fill(vis,vis+n+1,false);
	dis[Begin]=0;
	priority_queue<node>q;
	q.push({dis[Begin],Begin});
	while(q.size()){
		auto p=q.top();
		q.pop();
		if(!vis[p.se]){
			vis[p.se]=true;
			for(auto z:v[p.se]){
				if(!vis[z.fi]&&dis[z.fi]<dis[p.se]+z.se){
					dis[z.fi]=dis[p.se]+z.se;
					q.push({dis[z.fi],z.fi});
				}
			}
		}
	}
	return;
}
void TREE(){
	for(int i=1;i<=n;i++){
		for(auto z:v[i]){
			if(dis[z.fi]==dis[i]+z.se){
				fa[z.fi]=i;
			}
		}
	}
	return;
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	n++;
	for(int i=1,x,y,z;i<=m;i++){
		cin>>x>>y>>z;
		v[x].push_back({y,z});
	}
	Dijkstra(1);
	cout<<dis[n]<<'\n';
	TREE();
	for(int i=n;i;i=fa[i]){
		ans.push_back(i);
	}
	sort(ans.begin(),ans.end());
	for(auto z:ans){
		cout<<z<<' ';
	}
	return 0;
}