#include <string>
#include <vector>

using namespace std;

int answer;
int history=0;
vector<vector<vector<int>>> n_fares;
vector<vector<vector<int>>> list;

void update_list(int k, int n)//시작점, 길이
{
    int i,j,l, min1=0,ch;
    long min2=list[k][1][n-1]+1000000;
    int sum=list[k][1][n-1];
    for(i=0;i<n;i++){
        for(j=0;j<n_fares[1][list[k][0][i]].size();j++){
            ch=0;
            for(l=0;l<n;l++){
                if(n_fares[1][list[k][0][i]][j]==list[k][0][n-1]){
                    ch=1;
                    continue;
                }
            }
            if(ch==1) continue;
            if(min2>list[k][1][i]+n_fares[0][list[k][0][i]][j]){
                min2=list[k][1][i]+n_fares[0][list[k][0][i]][j];
                min1=n_fares[1][list[k][0][i]][j];
            }
        }
    }
    list[k][0].push_back(min1);
    list[k][1].push_back(min2);
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    answer = 0;
    history=0;
    int i,j,k;
    vector<int> ch(0,0);
    n_fares.resize(2, vector<vector<int>>(n, vector<int>(0,0)));//0==값,1==도착지
    list.resize(3, vector<vector<int>>(2, vector<int>(0,0)));// A/B/C,비용/지점, 길이
    
    for(i=0;i<fares.size();i++){
        n_fares[0][fares[i][0]-1].push_back(fares[i][2]);
        n_fares[0][fares[i][1]-1].push_back(fares[i][2]);
        n_fares[1][fares[i][0]-1].push_back(fares[i][1]-1);
        n_fares[1][fares[i][1]-1].push_back(fares[i][0]-1);
    }
    for(i=0;i<n_fares[0].size();i++){
        for(j=n_fares[0][i].size()-1;j>=0;j--){
            for(k=j-1;k>=0;k--){
                if(n_fares[0][i][j]<n_fares[0][i][k]){
                    answer=n_fares[0][i][j];
                    n_fares[0][i][j]=n_fares[0][i][k];
                    n_fares[0][i][k]=answer;
                    
                    answer=n_fares[1][i][j];
                    n_fares[1][i][j]=n_fares[1][i][k];
                    n_fares[1][i][k]=answer;
                }
            }
        }
    }
    answer=0;
    list[0][0].push_back(s-1);
    list[1][0].push_back(a-1);
    list[2][0].push_back(b-1);
    list[0][1].push_back(0);
    list[1][1].push_back(0);
    list[2][1].push_back(0);
    
    for(i=0;i<3;i++){
        update_list(0,list[0][0].size());
        update_list(1,list[0][0].size());
        update_list(2,list[0][0].size());
    }
    //return answer;
    return list[0][1][1];
}