#include<bits/stdc++.h> using namespace std; const int N=20,M=100; // 使用邻接表进行图的存储 int h[N],e[M],ne[M],w[M],idx; int state[N],dist[N]; int n,m; void add(int a,int b,int c){ e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } void Dijkstra(int x,int y){ // 由于存在多组数据，所以每次dist和st数组都需要初始化一遍 memset(dist,0x3f,sizeof dist); memset(state,0,sizeof state); // 设置源点的dist值为0 dist[x]=0; // 处理每个节点 for(int i=1;i<=n;i++){ // 查找当前距离源点最近的点t int t=-1; for(int j=1;j<=n;j++){ if(!state[j] && (t==-1 || dist[j]<dist[t])){ t=j; } } // 标记t点的状态 state[t]=1; // 对t点能够达到的点进行松弛操作 for(int j=h[t];j!=-1;j=ne[j]){ int v=e[j]; // 进行松弛 dist[v]=min(dist[v],dist[t]+w[j]); } } } int main(){ while(scanf("%d%d",&n,&m)!=EOF){ // end of file memset(h,-1,sizeof h); // 读入每一条表 while(m--){ int a,b,w; cin>>a>>b>>w; // 注意是无向图，要建立双向边 add(a,b,w),add(b,a,w); } int x,y; cin>>x>>y; Dijkstra(x,y); if(dist[y]!=0x3f3f3f3f) cout<<dist[y]<<endl; else cout<<"No path"<<endl; } return 0; }