#include <string>
#include <vector>

using namespace std;

int answer;
int min_;
int history=0;
vector<vector<vector<int>>> n_fares;
vector<vector<vector<int>>> list;
vector<vector<int>> v_list;
vector<vector<int>> count;



int update_list(int i,int k, int n)//시작점, 길이
{
    int j,l, min1=0,ch;
    long min2=list[k][1][n-1]+1000000;
    int sum=list[k][1][n-1];
    for(j=0;j<n_fares[1][list[k][0][i]].size();j++){
        ch=0;
        if(v_list[k][n_fares[1][list[k][0][i]][j]] != -1){
            if(list[k][0][v_list[k][n_fares[1][list[k][0][i]][j]]] > list[k][1][i]+n_fares[0][list[k][0][i]][j]){
                list[k][0][v_list[k][n_fares[1][list[k][0][i]][j]]]=list[k][1][i]+n_fares[0][list[k][0][i]][j];//값
                list[k][1][v_list[k][n_fares[1][list[k][0][i]][j]]]=n_fares[1][list[k][0][i]][j];//비용
                //정렬 필요
                v_list[k][n_fares[1][list[k][0][i]][j]]=
            }
        }
    }
    list[k][0].push_back(min1);
    list[k][1].push_back(min2);
    /*ch=0, sum=0;
    for(i=0;i<count[0].size();i++){
        if(count[0][i]==list[k][0][list[k][1].size()-1]){
            ch++;
            count[k+1][i]=list[k][1][list[k][1].size()-1];
            count[4][i]+=list[k][1][list[k][1].size()-1]-list[k][1][list[k][1].size()-2];
            if(count[1][i]>-1 && count[2][i]>-1 && count[3][i]>-1){
                if(count[4][i]<min_)
                    min_=count[4][i];
            }
        }
        if(count[k+1][i]<0){
            count[4][i]+=list[k][1][list[k][1].size()-1]-list[k][1][list[k][1].size()-2];
        }
        if(min_>count[4][i])
                sum=1;
    }
    if(ch==0){
        count[0].push_back(list[k][0][list[k][1].size()-1]);
        count[1].push_back(-1);
        count[2].push_back(-1);
        count[3].push_back(-1);
        count[4].push_back(list[0][1][list[0][0].size()-1]+list[1][1][list[1][0].size()-1]+list[2][1][list[2][0].size()-1]);
        count[k+1][count[k+1].size()-1]=list[k][1][list[k][1].size()-1];
    }
    if(sum){
        return 0;
    }
    return 1;*/
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    answer = 0;
    history=0;
    min_=2147483647;
    int i,j,k,exit=1, sum;
    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)));// s/a/b,비용/지점, 길이
    count.resize(5, vector<int>(0, 0));// 0=지점 1=s값 2=a값 3=b값 4=합계 5=완성유무
    v_list.resize(3, vector<int>(n, -1));//지점별 리스트 저장 순서
    
    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);
    
    v_list[0][s-1]=0;
    v_list[1][a-1]=0;
    v_list[2][b-1]=0;
    
    /*count[0].push_back(s-1);
    count[0].push_back(a-1);
    count[0].push_back(b-1);
    for(i=0;i<3;i++){
        count[1].push_back(-1);
        count[2].push_back(-1);
        count[3].push_back(-1);
        count[4].push_back(0);
        count[i+1][i]=0;
    }

    while(exit && n>=list[0][0].size()){
        for(i=0;i<3;i++){
            if(update_list(i,list[i][0].size()))
                exit=0;
        }
        exit++;
    }*/
    
    for(i=0; i<n;i++){
        for(j=0;j<3;j++){
            update_list(i, j,list[j][0].size());
        }
    }
    return min_;
}