//http://www.magicoj.com/contest/problem?id=923&pid=5#submit-code #include<iostream> #include<vector> #include<queue> #include<cstring> #define N 105 using namespace std; struct edge{ int v,w; }; struct node{ int dis,u; bool operator > (const node& a) const {return dis > a.dis;} }; priority_queue<node,vector<node>,greater<node>> q; vector<edge>e[N]; int dis[N],vis[N]; int n,m; void dijkstra(int st){ memset(dis,0x3f,(n+1) * sizeof(int)); memset(vis,0,(n+1) * sizeof(int)); dis[st] = 0; q.push({0,st}); while(!q.empty()){ int u = q.top().u; q.pop(); if(vis[u]) continue; vis[u] = 1; for(auto ed : e[u]){ int v = ed.v,w = ed.w; if(dis[v] > dis[u] + w){ dis[v] = dis[u] + w; q.push({dis[v],v}); } } } } int main(){ cin >> n >> m; for(int i = 0;i < m;i++) { int x,y,w; cin >> x >> y >> w; e[x].push_back({y,w}); } int a,b; cin >> a >> b; int ans = 0; dijkstra(a); ans += dis[b]; dijkstra(b); ans += dis[a]; cout << ans; }