#include<bits/stdc++.h> using namespace std; int dist[201][201],m,n,a,b; int main(){ ios::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(i==j) dist[i][j]=0; else dist[i][j]=0x3f3f3f3f; } } for(int i=1;i<=m;i++){ int a,b,wi; cin>>a>>b>>wi; dist[a][b]=wi; dist[b][a]=wi; } for(int t=1;t<=n;t++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(j!=i&&t!=i&&t!=j){ dist[i][j]=min(dist[i][j],dist[i][t]+dist[t][j]); } } } } while(cin>>a>>b){ if(dist[a][b]>0x3f3f3f3f-100000000) cout<<"No path"; else cout<<dist[a][b]; cout<<endl; } return 0; }