#include <string>
#include <vector>

using namespace std;

vector<vector<vector<int>>> n_fares;
vector<vector<int>> v_list;
vector<vector<int>> ch_list_;
vector<vector<int>> ch_list_2;
int c_list_min_;
int min_com;
int last_min_c[3];
int c_list_max_[3];
int asdf;
int last_ch;
int root[3];
int root_[3];

struct info {
    int coordinate;
    int cost;
    int last;
    int less;
    int more;
    int ch_;
    
    info() : coordinate(0), cost(0), last(0), less(0), more(0), ch_(0) {}

    info(int c1, int c2, int c3, int c4, int c5, int c6) : coordinate(c1), cost(c2), last(c3), less(c4), more(c5), ch_(c6) {}
};

vector<vector<info>> list;


void change_list(int k, int ch, int coordinate, int cost, int type){//ch==상위 값, n==새로운 값
    int i, size_=list[k].size();
    switch(type){
        case 0:
            list[k].push_back({coordinate,cost,list[k][ch].last,list[k][ch].less,ch,0});
            list[k][list[k][ch].less].last=size_;
            list[k][ch].less=-1;
            list[k][ch].last=size_;
            if(list[k][size_].last!=-1){
                if(list[k][list[k][size_].last].less==ch)
                    list[k][list[k][size_].last].less=size_;
                if(list[k][list[k][size_].last].more==ch)
                    list[k][list[k][size_].last].more=size_;
            }
            if(ch==root[k]) root[k]=size_;
            break;
        case 1:
            list[k].push_back({coordinate,cost,list[k][ch].last,ch,list[k][ch].more,0});
            list[k][list[k][ch].more].last=size_;
            list[k][ch].more=-1;
            if(list[k][size_].last!=-1){
                if(list[k][list[k][size_].last].less==ch)
                    list[k][list[k][size_].last].less=size_;
                if(list[k][list[k][size_].last].more==ch)
                    list[k][list[k][size_].last].more=size_;
            }
            list[k][ch].last=size_;
            if(ch==root[k]) root[k]=size_;
            break;
        case 2:
            list[k].push_back({coordinate,cost,ch,-1,-1,0});
            list[k][ch].less=size_;
            if(list[k][ch].last != -1 && list[k][ch].more==-1 && list[k][list[k][ch].last].less==ch && list[k][list[k][ch].last].more==-1){
                list[k][list[k][ch].last].less=-1;
                i=list[k][ch].last;
                list[k][ch].last=list[k][i].last;
                list[k][i].last=ch;
                list[k][ch].more=i;
                if(list[k][ch].last!=-1){
                    if(list[k][list[k][ch].last].less==i)
                        list[k][list[k][ch].last].less=ch;
                    if(list[k][list[k][ch].last].more==i)
                        list[k][list[k][ch].last].more=ch;
                }
                if(i==root[k]) root[k]=ch;
            }
            break;
        case 3:
            list[k].push_back({coordinate,cost,ch,-1,-1,0});
            list[k][ch].more=size_;
            if(list[k][ch].last != -1 && list[k][ch].less==-1 && list[k][list[k][ch].last].more==ch && list[k][list[k][ch].last].less==-1){
                list[k][list[k][ch].last].more=-1;
                i=list[k][ch].last;
                list[k][ch].last=list[k][i].last;
                list[k][i].last=ch;
                list[k][ch].less=i;
                if(list[k][ch].last!=-1){
                    if(list[k][list[k][ch].last].less==i)
                        list[k][list[k][ch].last].less=ch;
                    if(list[k][list[k][ch].last].more==i)
                        list[k][list[k][ch].last].more=ch;
                }
                if(i==root[k]) root[k]=ch;
            }
            break;
    }
}

void ch_list(int k, int coordinate, int cost){
    int i;
    int n_root=root[k];
    while(1){
        if(list[k][n_root].cost>cost){
            if(list[k][n_root].less==-1){
                change_list(k, n_root, coordinate, cost, 2);
                break;
            }
            if(list[k][n_root].less!=-1 && list[k][list[k][n_root].less].cost<cost && list[k][n_root].more==-1){
                change_list(k, n_root, coordinate, cost, 0);
                break;
            }else{
                n_root=list[k][n_root].less;
                continue;
            }
        }else{
            if(list[k][n_root].more==-1){
                change_list(k, n_root, coordinate, cost, 3);
                break;
            }
            if(list[k][n_root].more!=-1 && list[k][list[k][n_root].more].cost>cost && list[k][n_root].less==-1){
                change_list(k, n_root, coordinate, cost, 1);
                break;
            }else{
                n_root=list[k][n_root].more;
                continue;
            }
        }
    }
}

int update(int k, int coordinate){
    int i;
    int n_root=coordinate;
    int a=list[k][n_root].coordinate;
    int num=0;
    int sum;
    for(i=0;i<n_fares[0][a].size();i++){
        ch_list(k, n_fares[1][a][i], list[k][n_root].cost+n_fares[0][a][i]);
        num=list[k][list[k].size()-1].coordinate;
        
        sum=ch_list_[0][min_com]+ch_list_[1][min_com]+ch_list_[2][min_com];
        
        if(ch_list_[k][num]==-1 || ch_list_[k][num]>list[k][list[k].size()-1].cost){
            ch_list_[k][num]=list[k][list[k].size()-1].cost;
            //ch_list_2[k][num]=list[k][root_[k]].coordinate;
            
            if(ch_list_[0][num]!=-1 && ch_list_[1][num]!=-1 && ch_list_[2][num]!=-1){
                if(min_com==-1){
                    min_com=num;
                }
                else if(ch_list_[0][num]+ch_list_[1][num]+ch_list_[2][num]<sum){
                    min_com=num;
                }
            }
            
            /*if(((ch_list_[0][num]!=-1)?ch_list_[0][num] : list[0][root_[0]].cost)+
               ((ch_list_[1][num]!=-1)?ch_list_[1][num] : list[1][root_[1]].cost)+
               ((ch_list_[2][num]!=-1)?ch_list_[2][num] : list[2][root_[2]].cost)<=
               ((ch_list_[0][c_list_min_]!=-1)?ch_list_[0][c_list_min_] : list[0][root_[0]].cost)+
               ((ch_list_[1][c_list_min_]!=-1)?ch_list_[1][c_list_min_] : list[1][root_[1]].cost)+
               ((ch_list_[2][c_list_min_]!=-1)?ch_list_[2][c_list_min_] : list[2][root_[2]].cost)){
                    c_list_min_=num;
            }*/
        }
        /*if(min_com!=-1 && ch_list_2[1][min_com] != ch_list_2[2][min_com] &&
           ch_list_[0][min_com]+ch_list_[1][min_com]+ch_list_[2][min_com]<
           ((ch_list_[0][c_list_min_]!=-1)?ch_list_[0][c_list_min_] : list[0][root_[0]].cost)+
               ((ch_list_[1][c_list_min_]!=-1)?ch_list_[1][c_list_min_] : list[1][root_[1]].cost)+
               ((ch_list_[2][c_list_min_]!=-1)?ch_list_[2][c_list_min_] : list[2][root_[2]].cost) &&
          ch_list_[0][min_com]+ch_list_[1][min_com]+ch_list_[2][min_com]<list[0][root_[0]].cost+list[1][root_[1]].cost+list[2][root_[2]].cost){
            return 1;
        }*/
        if(min_com!=-1 && sum!=0 &&
          sum < list[0][root_[0]].cost &&
          sum < list[1][root_[1]].cost &&
          sum < list[2][root_[2]].cost){
            return 1;
        }
    }
    return 0;
}


int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    asdf=0;
    min_com=-1;
    int answer = 0,i, j, k, l;
    n_fares.resize(2, vector<vector<int>>(n, vector<int>(0,0)));//0==값 1==도착지
    list.resize(3, vector<info>());
    //sab,, 지점/비용/(비용이 더 작은 칸 번호)/(비용이 더 큰 칸 번호)/조사 상태(1==더작은검사완,2==해당칸검사완,3==더큰검사완),, 길이
    
    v_list.resize(3,vector<int>(n,0));
    ch_list_.resize(3,vector<int>(n,-1));
    ch_list_2.resize(3,vector<int>(n,-1));
    //c_list_min=2147483647;
    c_list_min_=0;
    //c_list_min_sum.resize(3,vector<int>(n,717483647));
    
    
    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);
    }
    
    list[0].push_back({s-1,0,-1,-1,-1,0});
    list[1].push_back({a-1,0,-1,-1,-1,0});
    list[2].push_back({b-1,0,-1,-1,-1,0});
    ch_list_[0][s-1]=0;
    ch_list_[1][a-1]=0;
    ch_list_[2][b-1]=0;
    ch_list_2[0][s-1]=0;
    ch_list_2[1][a-1]=0;
    ch_list_2[2][b-1]=0;
    v_list[0][s-1]=0;
    v_list[1][a-1]=0;
    v_list[2][b-1]=0;
    c_list_max_[0]=s-1;
    c_list_max_[1]=a-1;
    c_list_max_[2]=b-1;
    last_ch=0;
    root[0]=0;
    root[1]=0;
    root[2]=0;
    
    int pass=0;
    root_[0]=0;
    root_[1]=0;
    root_[2]=0;
    int endcount=0;
    int cost;
    int n_root;
    int num1=0;
    for(i=0;i<n;i++){
        for(k=0;k<3;k++){
            for(j=0;j<list[0].size();j++){
                num1=list[k][root_[k]].coordinate;
                if(root_[k]==-1 || num1==-1) return ch_list_[0][min_com] + ch_list_[1][min_com] + ch_list_[2][min_com];
                if(v_list[k][num1]==0 && list[k][root_[k]].ch_==0){
                    v_list[k][num1] = 1;
                    list[k][root_[k]].ch_ = 1;
                    break;
                }
                else if(list[k][root_[k]].ch_==0 && v_list[k][num1]!=0){
                    list[k][root_[k]].ch_ = 1;
                }
                if(list[k][root_[k]].ch_==1){
                    if(list[k][root_[k]].more==-1 || list[k][list[k][root_[k]].more].ch_==2){
                        list[k][root_[k]].ch_ = 2;
                        root_[k] = list[k][root_[k]].last;
                        continue;
                    }
                    root_[k] = list[k][root_[k]].more;
                    if(list[k][root_[k]].ch_!=0)
                        continue;
                    if(list[k][root_[k]].less!=-1){
                        while(list[k][root_[k]].less!=-1 && list[k][list[k][root_[k]].less].ch_==0){
                            root_[k] = list[k][root_[k]].less;
                        }
                    }
                    continue;
                }
                if(list[k][root_[k]].ch_==2){
                    root_[k] = list[k][root_[k]].last;
                }
            }
            if(root_[k]==-1 || num1==-1) return ch_list_[0][min_com] + ch_list_[1][min_com] + ch_list_[2][min_com];
            while(list[k][root[k]].cost<list[k][root_[k]].cost){
                root[k]=list[k][root[k]].more;
            }
            if(update(k, root_[k])) {
                i=n;
                //return asdf;
                break;
            }
        }
    }
    
    return ch_list_[0][min_com] + ch_list_[1][min_com] + ch_list_[2][min_com];
}