rt，一年前的题翻出来还是不会

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
struct e{int v,w;};
vector<e> g[10001];
int n,m,d[10001],p[10001],inq[10001],tir[10001];
queue<int> q;
void out(int x){
	if(!x) return;
	out(p[x]);
	printf("%d ",x);
}
int main(){
	memset(d,127,sizeof(d));
	scanf("%d%d",&n,&m);
	for(int i=1,a,b,c;i<=m;i++){
		scanf("%d%d%d",&a,&b,&c);
		g[a].push_back({b,c});
	}
	d[1]=0;
	q.push(1);
	inq[1]=1;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		inq[u]=0;
		for(auto v:g[u]){
			if(d[v.v]>d[u]+v.w+tir[u]){
				d[v.v]=d[u]+v.w+tir[u];
				p[v.v]=u,tir[v.v]=tir[u]+1;
				if(!inq[v.v]) q.push(v.v),inq[v.v]=1;
			}
		}
	}
	printf("%d\n",d[n]);
	out(n);
}