#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;

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;
    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;
            break;
        case 1:
            list[k].push_back({coordinate,cost,list[k][ch].last,list[k][ch].more,ch,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;
            break;
        case 2:
            list[k].push_back({coordinate,cost,ch,-1,-1,0});
            list[k][ch].less=list[k].size()-1;
            if(list[k][ch].more==-1 && 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;
            }
            break;
        case 3:
            list[k].push_back({coordinate,cost,ch,-1,-1,0});
            list[k][ch].more=list[k].size()-1;
            if(list[k][ch].less==-1 && 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;
            }
            break;
    }
}

void ch_list(int k, int coordinate, int cost){
    int i;
    int n_root=root;
    for(i=0;i<200;i++){
        if(list[k][n_root].cost>cost){
            if(list[k][list[k][n_root].less].cost<cost){
                if(list[k][n_root].more==-1){
                    change_list(k, list[k][n_root].last, coordinate, cost, 0);
                    break;
                }
                n_root=list[k][n_root].more;
                continue;
            }
        }
    }
}

void update(int k, int n){
    int i;
    int a=list[k][n].coordinate;
    for(i=0;i<n_fares[k][a].size();i++){
        
    }
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    asdf=0;
    int answer = 0,i;
    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(5,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;
    

    
    return c_list_min;
}