import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;
class Edge{
    int dst, cost;
    public Edge(int dst, int cost) {
        this.dst = dst;
        this.cost = cost;
    }
}
class Solution {
    static int ans = 987654321;
    static int dist[], dp[][];
    static List<Edge> adj[];
    public static int solution(int n, int s, int a, int b, int[][] fares) {
        dist = new int[n + 1];
        Arrays.fill(dist, 987654321);
        adj = new List[n + 1];
        dp = new int[n + 1][n + 1];
        for (int i = 0; i <= n; i++) {
            adj[i] = new ArrayList<>();
            Arrays.fill(dp[i], 987654321);
        }
        for (int[] fare : fares) {
            int u = fare[0];
            int v = fare[1];
            int c = fare[2];
            dp[u][v] = dp[v][u] = c;
            adj[u].add(new Edge(v, c));
            adj[v].add(new Edge(u, c));
        }
        getFloyd(n);
        dijkstra(s, a, b);
        return ans;
    }
    private static void getFloyd(int n) {
        for (int k = 1; k <= n ; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if(i == j) dp[i][j] = 0;
                    else{
                        if(dp[i][j] > dp[i][k] + dp[k][j])
                            dp[i][j] = dp[i][k] + dp[k][j];
                    }
                }
            }
        }
    }
    private static void dijkstra(int s, int a, int b) {
        PriorityQueue<Edge> pq = new PriorityQueue<>((c, d) -> (c.cost - d.cost));
        pq.add(new Edge(s, 0));
        dist[s] = 0;
        while (!pq.isEmpty()) {
            Edge now = pq.poll();
            int cur = now.dst, curCost = now.cost;
            if(dist[cur] < curCost) continue;
            ans = Math.min(ans, curCost + dp[cur][a] + dp[cur][b]);
            for (Edge edge : adj[cur]) {
                int next = edge.dst;
                int nextCost = edge.cost;
                if(dist[next] > curCost + nextCost){
                    dist[next] = curCost + nextCost;
                    pq.add(new Edge(next, dist[next]));
                }
            }
        }
    }
}