#include <string>
#include <vector>

using namespace std;

vector<vector<vector<int>>> n_fares;
vector<vector<int>> v_list;
vector<vector<int>> ch_list_;
//int c_list_min;
int c_list_min_;
int min_com;
int c_list_max_[3];
//vector<vector<int>> c_list_min_sum;
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;
    //if(cost==0) asdf+=100000000;
    //if(k==0 && cost==34) asdf=type;
    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=list[k].size()-1;
            list[k][ch].less=-1;
            list[k][ch].last=list[k].size()-1;
            //if(k==0) asdf+=1;
            if(ch==root[k]) root[k]=list[k].size()-1;
            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=list[k].size()-1;
            list[k][ch].more=-1;
            list[k][ch].last=list[k].size()-1;
            //if(k==0) asdf+=100;
            if(ch==root[k]) root[k]=list[k].size()-1;
            break;
        case 2:
            //if(k==0) asdf+=10000;
            list[k].push_back({coordinate,cost,ch,-1,-1,0});
            list[k][ch].less=list[k].size()-1;
            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){
                //if(k==0 && ch==0) asdf+=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;
            }
            //if(k==0 && cost==51) asdf=ch;
            break;
        case 3:
            //if(k==0 && ch==1 && coordinate==3) asdf=list[k][ch].last;
            list[k].push_back({coordinate,cost,ch,-1,-1,0});
            list[k][ch].more=list[k].size()-1;
            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){
                //if(k==0) asdf+=1;
                //if(k==0) asdf=list[k][list[k][ch].last].last;
                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(k==0 && ch==0) asdf=ch;
                if(i==root[k]) root[k]=ch;
                //if(k==0 && cost==34) asdf=1000;
            }
            //if(k==0 && cost==20) asdf=list[k][ch].more;
            break;
    }
    //if(k==0) asdf=list[k][list[k].size()-1].coordinate;
}

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;
    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;
        
        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;
            
            if(ch_list_[0][num]!=-1 && ch_list_[1][num]!=-1 && ch_list_[2][num]!=-1){
                if(min_com==-1){
                    //asdf++;
                    min_com=num;
                }
                else if(ch_list_[0][num]+ch_list_[1][num]+ch_list_[2][num]<ch_list_[0][min_com]+ch_list_[1][min_com]+ch_list_[2][min_com]){
                    min_com=num;
                    //asdf++;
                }
            }
            
            //if(ch_list_[k][c_list_max_[k]]<ch_list_[k][num]) c_list_max_[k]=num;
            
            if(((ch_list_[0][min_com]!=-1)?ch_list_[0][num] : list[0][root_[0]].cost)+
               ((ch_list_[1][min_com]!=-1)?ch_list_[1][num] : list[1][root_[1]].cost)+
               ((ch_list_[2][min_com]!=-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)){
                //asdf=c_list_min_;
                //if(ch_list_[0][num]==-1 || ch_list_[1][num]==-1 || ch_list_[2][num]==-1)
                    c_list_min_=num;
            }
        }
        if(min_com!=-1 && 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)){
            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));
    //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;
    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;
    //if(b!=1) return -1;
    for(i=0;i<n;i++){
        for(k=0;k<3;k++){
            //if(i==0 && k==1) return list[0].size();
            //if(i==2 && k==0) return v_list[k][list[k][list[k][root_[k]].more].coordinate];
            for(j=0;j<list[0].size();j++){
                if(i==4 && j==5 && k==0){
                    //return list[k][list[k][root_[k]].less].cost;
                }
                if(root_[k]==-1 || list[k][root_[k]].coordinate==-1) return asdf;
                if(v_list[k][list[k][root_[k]].coordinate]==0 && list[k][root_[k]].ch_==0){
                    v_list[k][list[k][root_[k]].coordinate] = 1;
                    list[k][root_[k]].ch_ = 1;
                    //if(i==2 && k==0) asdf++;
                    break;
                }
                else if(list[k][root_[k]].ch_==0 && v_list[k][list[k][root_[k]].coordinate]!=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;
                        //asdf=root_[k];
                        root_[k] = list[k][root_[k]].last;
                        //if(root_[k]==-1 || list[k][root_[k]].coordinate==-1) return root_[k];
                        continue;
                    }
                    root_[k] = list[k][root_[k]].more;
                    //if(root_[k]==-1 || list[k][root_[k]].coordinate==-1) return 10;
                    if(list[k][root_[k]].ch_!=0)
                        continue;
                    if(list[k][root_[k]].less!=-1){
                        for(l=0;l<list[0].size();l++){
                            if(list[k][root_[k]].less!=-1 && list[k][list[k][root_[k]].less].ch_==0){
                                root_[k] = list[k][root_[k]].less;
                               // if(root_[k]==-1 || list[k][root_[k]].coordinate==-1) return 1000;
                                continue;
                            }
                            break;
                        }
                    }
                    continue;
                }
                if(list[k][root_[k]].ch_==2){
                    root_[k] = list[k][root_[k]].last;
                    //if(root_[k]==-1 || list[k][root_[k]].coordinate==-1) return 10000;
                }
            }
            //if(i==2 && k==0) return list[0][root_[0]].coordinate;
            //update(k, root_[k]);
            //if(b==1 && k==0 && i==1) return list[k][root_[k]].coordinate;
            if(root_[k]==-1 || list[k][root_[k]].coordinate==-1) return asdf;
            //if(k==1 && i==4) return list[k][root_[k]].coordinate;
            if(k==0) asdf=asdf*10+list[k][root_[k]].coordinate;
            //update(k, root_[k]);
            if(update(k, root_[k])) {
                //return ch_list_[0][min_com];//list[0][13].cost;
                i=n;
                break;
            }
        }
    }
    

    //ch_list(int k, int coordinate, int cost)
    /*ch_list(0, 10, 10);
    ch_list(0, 5, 11);
    */
    
    /*return asdf;/*ch_list_[2][c_list_min_];/*((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);*/
    //return asdf;
    return ch_list_[0][min_com] + ch_list_[1][min_com] + ch_list_[2][min_com];
    //return ch_list_[2][c_list_max_[2]];
    return list[0][7].last;
    return list[0][list[0][list[0][list[0][list[0][0].last].last].last].less].cost;
    return list[0][0].last;
    return list[0][0].less;
    return list[0][0].more;
    return list[0][0].coordinate;
    //return list[0][list[0][0].last].last;
    return list[0][list[0][list[0][0].last].less].coordinate;
}