#include <iostream> #include <vector> #include <queue> #include <climits> using namespace std; typedef pair<int, int> pii; vector<int> dijkstra(int start, int n, const vector<vector<pii>>& graph) { vector<int> dist(n+1, INT_MAX); priority_queue<pii, vector<pii>, greater<pii>> pq; dist[start] = 0; pq.push({0, start}); while (!pq.empty()) { int u = pq.top().second; int d = pq.top().first; pq.pop(); if (d > dist[u]) continue; for (auto& edge : graph[u]) { int v = edge.first; int w = edge.second; if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; pq.push({dist[v], v}); } } } return dist; } int main() { int N, M; cin >> N >> M; vector<vector<pii>> graph(N+1); for (int i = 0; i < M; ++i) { int u, v, cost; cin >> u >> v >> cost; graph[u].push_back({v, cost}); } int A, B; cin >> A >> B; vector<int> distA = dijkstra(A, N, graph); vector<int> distB = dijkstra(B, N, graph); cout << distA[B] + distB[A] << endl; return 0; }