dix[]保存到终点的最短权值，d[]保存到终点的最短边长
结构体保存边和权值，二维数组太大用不了;
一直Runtime Error.....
#include<iostream>
#include<cstring>
#include<set>
#include<vector>
#include<cstdio>
#include<queue>
#include<cctype>
using namespace std;
const int INF=(1<<30);
const int maxn=100005;
int d[maxn],n,dix[maxn],ans[maxn],k;
struct Line
{int u,v,weight;Line(int u=0,int v=0,int weight=0) :u(u),v(v),weight(weight) {}
}G[maxn*2];
void print(int* A,int n)
{for(int i=0;i<n;i++){if(i) putchar(' ');printf("%d",A[i]);}printf("\n");
}
void bfs()
{queue<int> q;q.push(n);d[n]=0;for(int i=1;i<n;i++)d[i]=INF;dix[n]=0;for(int i=1;i<n;i++)dix[i]=INF; int vis[maxn]={0};vis[n]=1;while(!q.empty()){int u=q.front();q.pop();for(int i=0;i<k;i++){ int v=G[i].u,nu=G[i].v;if(nu==u&&!vis[v]){if(d[v]>1+d[u])d[v]=d[u]+1;if(dix[v]>dix[u]+G[i].weight)dix[v]=dix[u]+G[i].weight;vis[v]=1;q.push(v);}}}}
int ans_bfs()
{int u=1;int p=0;ans[p++]=1;while(u!=n){int mv=INF,mw=INF;for(int v=1;v<=n;v++){if(d[u]-d[v]==1&&mw>dix[v]){mv=v;mw=dix[v];}}u=mv;ans[p++]=mv;}return p-1;
}
int main()
{while(scanf("%d%d",&n,&k)!=EOF){memset(G,0,sizeof(G));for(int i=0;i<k;i++){int x,y,m;scanf("%d%d%d",&x,&y,&m);G[i].u=x;G[i].v=y;G[i].weight=m;}bfs();k=ans_bfs();printf("%d\n",k);print(ans,k); }return 0;
}