#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_;
//vector<vector<int>> c_list_min_sum;
int asdf;
int last_ch;
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;
    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){
                //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(i==root[k]) root[k]=ch;
            }
            break;
        case 3:
            if(k==0) asdf+=1000000;
            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){
                //if(k==0 && ch==0) asdf+=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(k==0 && ch==0) asdf=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];
    for(i=0;i<200;i++){
        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;
            }
        }
    }
}

void update(int k, int coordinate){
    int i;
    int n_root=coordinate;
    int a=list[k][n_root].coordinate;
    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]);
        /*if(ch_list_[k][list[k][list[k].size()-1].coordinate]>list[k][list[k].size()-1].cost){
            ch_list_[k][list[k][list[k].size()-1].coordinate]=list[k][list[k].size()-1].cost;
        }*/
    }
}


int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    asdf=0;
    int answer = 0,i, j, k;
    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,-1));
    ch_list_.resize(4,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});
    last_ch=0;
    root[0]=0;
    
    int pass=0;
    int root_[3]={0};
    for(i=0;i<n;i++){
        for(k=0;k<3;k++){
            pass=0;
            for(j=0;j<list[0].size();j++){
                switch((list[k][root_[k]].more!=-1 || list[k][root_[k]].ch_==0) ? list[k][root_[k]].ch_ : 2){
                    case 0:
                        pass=1;
                        list[k][root_[k]].ch_=1;
                        break;
                    case 1:
                        root_[k]=list[k][root_[k]].more;
                        break;
                    case 2:
                        root_[k]=list[k][root_[k]].last;
                        break;
                }
                if(pass==1) break;
            }
            update(k, root_[k]);
        }
    }
    
    
    
    //ch_list(int k, int coordinate, int cost)
    /*ch_list(0, 10, 10);
    ch_list(0, 5, 11);
    */
    //return asdf;
    return list[0][root_[0]].coordinate;
    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;
}