#include<iostream> #include<vector> #include<queue> using namespace std; int main() { cin.tie(nullptr)->sync_with_stdio(false); int n,r; cin>>n; cin>>r; vector<pair<int,int>> s; vector<int> dist; vector<vector<pair<int,int>>> adj(n); int temp1,temp2; cin>>temp1; cin>>temp2; s.push_back({temp1,temp2}); cin>>temp1; cin>>temp2; s.push_back({temp1,temp2}); for(int i=0;i<r;i++) { int u,v,w; cin>>u; cin>>v; cin>>w; u--; v--; adj[u].push_back({v,w}); adj[v].push_back({u,w}); } /*for(int i=0;i<n;i++) { for(int j=0;j<adj[i].size();j++) { cout<<i<<" "<<adj[i][j].first<<" "; } cout<<"\n"; }*/ ////////////////////////////////////////////////////////// priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>> > q; dist.resize(n,1e9+7); //////////////////////////////////////////////////////////////////// dist.assign(n,1e9+7); dist[s[1].first-1]=0; q.push({0,s[1].first-1}); while(!q.empty()) { int a,b; a=q.top().first; b=q.top().second; q.pop(); for(pair<int,int>& x:adj[b]) { if(dist[x.first]<=x.second+a) { continue; } dist[x.first] = x.second+a; q.push({dist[x.first], x.first}); } } int ans; ans=dist[s[1].second-1]; cout<<ans; }