1 #include <stdio.h>  2 #include <iostream>  3 #include<queue>  4 #include <string.h>  5 #include <algorithm>  6 #define maxn 200009  7 using namespace std;  8 typedef pair<int,int>pii;  9 int head[maxn],next[maxn],point[maxn],value[maxn],now=0; 10 int n,m,maxx=-1,po,dist[maxn],x,y,z,k,v[maxn],dp[maxn],egz[maxn]; 11 int an=0,pp[maxn],final[maxn],oo=0; 12 int num[maxn],route[maxn]; 13  14 void add(int x,int y,int v,int zz) 15 { 16     next[++now]=head[x]; 17     head[x]=now; 18     point[now]=y; 19     value[now]=v; 20     num[now]=zz; 21 } 22 struct cmp 23 { 24     bool operator()(pii a,pii b) 25     { 26         return a.first>b.first; 27     } 28 }; 29 void dijkstra(int s) 30 { 31     memset(dist,-1,sizeof(dist)); 32     dist[s]=0; 33     priority_queue<pii,vector<pii>,cmp>q; 34     q.push(make_pair(0,s)); 35     while(!q.empty()) 36     { 37         pii u=q.top(); 38         q.pop(); 39         if(u.first>dist[u.second])continue; 40         for(int i=head[u.second];i!=0;i=next[i]) 41         { 42             int k=point[i]; 43             if(dist[u.second]+value[i]<dist[k] || dist[k]==-1) 44             { 45                 dist[k]=dist[u.second]+value[i]; 46                 q.push(make_pair(dist[k],k)); 47             } 48         } 49     } 50 } 51 /* 52 void spfa(int s,int o) 53 { 54     int visit[maxn]={0}; 55     queue<int>q; 56     for(int i=1;i<=n;i++)dist[i]=-1; 57     dist[s]=0; 58     visit[s]=1; 59     q.push(s); 60     while(!q.empty()) 61     { 62         int u=q.front(); 63         q.pop(); 64         visit[u]=0; 65         for(int i=head[u];i!=0;i=next[i]) 66         { 67             int k=point[i]; 68             if(dist[u]+value[i]<dist[k]|| dist[k]==-1) 69             { 70                 dist[k]=dist[u]+value[i]; 71                 if(visit[k]==0) 72                 { 73                     visit[k]=1; 74                     q.push(k); 75                 } 76             } 77         } 78     } 79 } 80 */ 81 int dfs(int s,int b) 82 { 83     if(dp[s]!=-1)return dp[s]; 84     int ans=0; 85     for(int i=head[s];i!=0;i=next[i]) 86     { 87         int u=point[i]; 88         if(dist[u]!=dist[s]+value[i])continue; 89         int val=dfs(u,(egz[s]?b+1:b)); 90         if(val>ans) 91         { 92             ans=val; 93             pp[s]=u; 94             route[s]=num[i]; 95             if(val==k-1)break; 96         } 97     } 98     return dp[s]=ans+(egz[s]==1?1:0); 99 }100 int main()101 {102     scanf("%d%d",&n,&m);103     for(int i=1;i<=m;i++)104     {105         scanf("%d%d%d",&x,&y,&z);106         add(x,y,z,i);107         add(y,x,z,i);108     }109     scanf("%d",&k);110     for(int i=1;i<=k;i++){scanf("%d",&v[i]);egz[v[i]]=1;}111     dijkstra(v[1]);112     for(int i=1;i<=k;i++)if(dist[v[i]]>maxx)113     {114         maxx=dist[v[i]];115         po=v[i];116     }117     dijkstra(po);118     memset(dp,-1,sizeof(dp));119     dfs(po,1);120     an=po;121     while(pp[an]!=0)122     {123         final[++oo]=route[an];124         an=pp[an];125     }126     printf("%d\n",oo);127     for(int i=1;i<=oo-1;i++)printf("%d ",final[i]);128     printf("%d",final[oo]);129     return 0;130 }